Theta for dummies, oder: Asymptotisches Wachstum von Funktionen

  • Nabend,
    ich hab mal im Zuge der Lernsession für den morgigen Test eine Art Howto für diesen Bereich geschrieben.


    Verbesserungsvorschläge und Korrekturen sind gern gesehen und werden natürlich in Updates dieses Dokuments einfließen.


    Hoffentlich hilfts jemanden :D

    Files

    Edited 5 times, last by phpwutz: hinweis zur Konstantenwahl eingefügt, beispiel 1 tippfehler korrigiert ().

  • Hallo,


    schöne Anleitung, aber ich kann nicht nachvollziehen, wie Du auf Werte 1 und 10 für die Konstante c1 und c2 (Seite 3) kommst - die müssten doch 4 und 6 sein, oder? s. Anhang


    Danke!


    Viele Grüße
    Asg


    konstante.jpg

  • Im Grunde richtig, da gehören eigentlich c1 = 4 und c2 = 6 rein.
    jedes c1 < 4 und jedes c2 > 6 sind allerdings genauso richtige Antworten. Alle Klarheiten beseitigt? :D


    /pdf updated

  • Die Klarheiten waren eigentlich schon mit deinem Beispiel beseitigt, aber ich wollte sie nochmals desinfiziert haben :D:D:thumb:


    Danke für die Korrektur der Pdf!


    Viele Grüße
    Asg

  • Es wäre super wenn jmd mich erklärt wie kommt man c1=4 an . Ist es mathematsich überhaupt möglich ? Ich hab die gleiches Problem in der Skriptum st 23 mit c2 in Bspl 1. Soll n nicht immer größer als 0 gewählt werdenn ?

  • Hallo,


    Es wäre super wenn jmd mich erklärt wie kommt man c1=4 an . Ist es mathematsich überhaupt möglich ?


    Die Gleichung ist doch ok:

    Code
    1. 0 <= 4 < 5/5 + 5 <= 6


    Oder was meinst du genau?


    Ich hab die gleiches Problem in der Skriptum st 23 mit c2 in Bspl 1. Soll n nicht immer größer als 0 gewählt werdenn ?


    Hier kann ich dir nicht folgen, welchse Beispiel?


    Viele Grüße
    Asg

  • Sorry für die unklarheit . Was ich nicht verstehe ist wie kann man c1 4 finden in der ungleichheit in Bspl 4.1. Also c1 <= 15/n + 5 <= c2 . Ich meine , auch wenn ich 15/n als 0 annehme kleinste Wert für c1 bleibt 5 . Auch bei der Beispiel in Skriptum mit der Ungleichheit . c1<= 1/2 - 3/n <= c2 . Wie kann kann es hier gelten für alle n>=1 , wenn c2>= 1/2

  • Hallo,


    [...] Also c1 <= 15/n + 5 <= c2 . Ich meine , auch wenn ich 15/n als 0 annehme kleinste Wert für c1 bleibt 5 .


    ich denke da hast du einen Denkfehler oder ich verstehe dich nicht ganz: ob wir 15/n durch 0 ersetzen oder nicht, ändert es nichts an der Sache. Wenn wir 15/n durch 0 ersetzen, dann haben wir ja folgendes:


    Code
    1. c1 <= 0 + 5 <= c2
    2. c1 <= 5 <= c2


    Und wenn wir nun c1 = 4 und c2 = 6 setzen, dann lautet die Gleichung:

    Code
    1. 4 <= 5 <= 6


    Und das stimmt ja, denn 4 ist kleiner-gleich 5 UND 5 ist kleiner-gleich 6.


    Kleiner-Gleich bedeutet ja hier:
    1. 4 ist ENTWEDER kleiner als 5 ODER
    2. 4 ist gleich 5


    Wenn eine der beiden Aussagen WAHR ist, dann ist die Ungleichung gültig und hier ist ja die 1. Aussage WAHR (4 ist kleiner als 5).


    [...]Auch bei der Beispiel in Skriptum mit der Ungleichheit . c1<= 1/2 - 3/n <= c2 . Wie kann kann es hier gelten für alle n>=1 , wenn c2>= 1/2


    Wo steht das?


    Viele Grüße
    Asg

  • Erst mal danke für dein howto :)


    Nach der 1. Vorlesung sollen wir nun direkt Übungsaufgaben bearbeiten. Wir haben noch nichtmal ein Skript.


    Meine Aufgabe sieht folgendermaßen aus


    Die Funktion T1(n) liegt in O(n3). Leiten Sie entsprechende Konstanten c1 und c2 ab, um zu zeigen, dass T1(n) "Element" O(n3) gilt. T1(n) = 2n3 + 7n - 10


    Was ich aus dem howto weiß ist, dass ich nun n0 und c1 brauche, sodass gilt: 0 <= f(n) <= c1 * g(n)
    richtig?


    Ich versteh allerdings nicht, wieso in dem Beispiel steht, dass gilt T(n) = 0(n2)
    Wieso n2?