aufgabe 4 ? wie rechnet man das
Results 1 to 9 of 9
  1. #1

    Title
    Principal
    Join Date
    Oct 2002
    Posts
    38
    Thanks
    0
    Thanked 0 Times in 0 Posts

    aufgabe 4 ? wie rechnet man das

    ich blick da nicht ganz durch

    n³ + wurzel aus n >= n³ richtig
    n³ + wurzel aus n <= n³ sollte doch falsch sein
    n^3<= n³ + wurzel n >= n³ -"-
    n²>=n^3+wurzel n falsch

  2. #2

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    Wenn man die Definitionen der Notationen O, \Omega und \Theta (Skriptum, Seite 17) ins "Deutsche" uerbersetzt, erahelt man sinngemaesz folgendes:

    Fuer \Theta:

    f(n) = \Theta(g(n)) <=> man kann f(n)/g(n) zwischen zwei Konstanten c_1 und c_2 einschlieszen. Das muss nicht einmal fuer alle n gelten, sondern nur fuer alle n >= n_0. Wobei c_1, c_2 und n_0 Konstanten sind die nur groeszer als 0 sein muessen.

    Wenn man diese drei Konstanten finden kann, dann ist f(n) = \Theta(g(n)).

    Analog sieht es bei O und \Omega aus, nur dass man eben bei O die kleinere und bei \Omega die groeszere Konstante nicht braucht. Daraus folgt auch, dass wenn eine Funkion in \Theta(g(n)) ist, dann ist sie auch in O(g(n)) und in \Omega(g(n)).

    Beweis fuer n^3 + sqrt(n) = \Theta(n^3):

    0 <= c_1 * n^3 <= n^3 + sqrt(n) <= c_2 * n^3 | :n^3
    0 <= c_1 <= n^3/n^3 + sqrt(n)/n^3 <= c_2

    Diese Ungleichung gilt zum Beispiel fuer:

    c_1 = 1
    c_2 = 2
    n_0 = 1

    Analog kann man dann zeigen, dass n^3 + sqrt(n) != O(n^2).

    /edit 15.10.02:
    Rechtschreibfehler.
    Last edited by yrucrem; 15-10-2002 at 20:56.

  3. #3

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    702
    Thanks
    0
    Thanked 0 Times in 0 Posts
    und wie würde ds für die erste gleichung f(n)= o,5n^2 lauten?
    warum müssen wir das nicht berechnen....nur weil wir nur für große n0 rechnen müssen...??? das ist eine begründung?

  4. #4

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    Ja. Man darf die Konstanten c_1, c_2 und n_0 beliebig waehlen. Sie muessen nur groeszer 0 sein. Wenn wir also n_0 gleich auf 1000 setzten keonnen wir die erste Formel ignorieren.

    Der vollastaendigkeit halber:

    0.5n^2 != \Omega(n^3) (n^3 ist sicher keine untere Schranke von n^2)

    0.5n^2 = O(n^3) (n^3 ist eine obere Schranke von n^2)

    0.5n^2 != \Theta(n^3) (dann muesste es auch in O(n^3) _und_ \Omega(n^3) sein)

    0.5n^2 = O(n^2) (n^2 ist natuerlich eine obere schranke von n^2)

  5. #5

    Title
    Principal
    Join Date
    Oct 2002
    Posts
    38
    Thanks
    0
    Thanked 0 Times in 0 Posts
    f=o(n^3) aber wie kann das stimmen -->
    n^3+sqrt(n)<=n^3 ist doch falsch

    oder stell ich die ungleichungen falsch auf ?

  6. #6

    Title
    Elite
    Join Date
    Oct 2002
    Location
    Wien
    Posts
    300
    Thanks
    6
    Thanked 1 Time in 1 Post
    pass mal auf..
    fuer O(n^3) brauchst du ne obere schranke..
    die ungleichung lautet n^3+sqrt(n)<=c * n^3
    du hast die konstante vergessen...
    mfg funkywon

  7. #7
    Pinkman's Avatar
    Title
    Elite
    Join Date
    Oct 2010
    Posts
    358
    Thanks
    45
    Thanked 46 Times in 37 Posts
    Quote Originally Posted by yrucrem View Post
    f(n) = \Theta(g(n)) <=> man kann f(n)/g(n) zwischen zwei Konstanten c_1 und c_2 einschlieszen. Das muss nicht einmal fuer alle n gelten, sondern nur fuer alle n >= n_0. Wobei c_1, c_2 und n_0 Konstanten sind die nur groeszer als 0 sein muessen.

    Beweis fuer n^3 + sqrt(n) = \Theta(n^3):
    0 <= c_1 * n^3 <= n^3 + sqrt(n) <= c_2 * n^3 | :n^3
    0 <= c_1 <= n^3/n^3 + sqrt(n)/n^3 <= c_2

    Diese Ungleichung gilt zum Beispiel fuer:
    c_1 = 1
    c_2 = 2
    n_0 = 1
    Was ich jetzt nicht verstehe: c1,c2 und n0 sind so gewählt, dass sie für alle n0 >= n0 gelten müssen. Wenn ich jetzt aber zB n=9 einsetze, stimmt das ganze nicht mehr, weil dann 3/729 rauskommt, und das ist aber kleiner als das gewählte c1. Dann stimmt die Ungleichung ja nicht mehr?
    YEAH SCIENCE!
    ------------------
    EVC Tutor + Organisation SS 2016

  8. #8

    Title
    Principal
    Join Date
    Mar 2011
    Location
    Matzendorf
    Posts
    73
    Thanks
    0
    Thanked 13 Times in 10 Posts
    0<=729<=732<=1458 stimmt doch eh! Wo kommt da 3/729 raus????

  9. #9
    Pinkman's Avatar
    Title
    Elite
    Join Date
    Oct 2010
    Posts
    358
    Thanks
    45
    Thanked 46 Times in 37 Posts
    Oh gott, ich hab übersehen, dass n³/n³ = 1, und nicht gleich 0 ist *_*
    Dann passen die Werte...Tschuldigung...

    (Ich probe mal für n=9:
    1 <= 1+ sqrt(9)/9³ <= 2; wenn man c1=1, c2=2 und n0=0 wählt. Und egal wie riesig ich n wähle, das wird immer unter 2 bleiben. Jabba dabba du.)
    YEAH SCIENCE!
    ------------------
    EVC Tutor + Organisation SS 2016

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •