Video 3-3: Asymptotische Notation

0:02 Auf Basis von diesen Grenzwerten können wir jetzt endlich unsere asymptotische Notation definieren. Und wir werden sehen, in den meisten Anwendungsfällen müssen wir nicht auf diese Definition runter, sondern können mit mit sehr viel einfachen Argumenten hantieren bzw. Abkürzung nehmen für Funktionen, mit denen wir häufig arbeiten.

0:22 Da sie das vielleicht schon gesehen haben, dachte ich, ich ähm sage Sie mal zu etwas, wovon Sie nach unserem Currikulum, soweit ich es kenne, ähm nicht unbedingt wissen, was die Antwort ist, aber wir können ja mal schauen. Und wenn sie die Antwort nicht kennen oder alle bei keine Ahnung oder sonst wo ihr Kreuz machen, ist das vollkommen okay. Die Frage ist so ein bisschen, wie viel ähm Details lohnt es sich hier im Plenum durchzugehen oder wie viel wollen wir in die Übung packen oder langweilen wir sie womöglich damit?

1:53 Also, wir waren ja mal bei etwa 60. Da sind wir jetzt fast ah die letzten noch reingesprungen. Also, ich zeige ihn erstmal nur, was so ähm das Meinungsbild ergibt. Sind doch sehr viele, die ohne Dation noch nicht gesehen haben oder zumindest nicht sicher sind, was ich hier eigentlich will. Ähm, vollkommen in Ordnung. ähm lassen sich auch nicht beeinflussen. Also nur weil hier so ein paar äh sicher sind, heißt es ja nicht, dass die recht haben. Zumal sich auch die Denke ja und die ja bin mir sicher Fraktion auch nicht einig sind. Äh kommen wir noch mal dazu darauf zurück. Noch mal ein Schritt zurück. Was wollen wir? Wir analysieren Algorithmen. Ich hatte gesagt, das Hauptding, warum Algorithmen besser oder schlechter sind als andere, ist, wie skalieren ihre Kosten, wenn wir die Eingabe immer größer machen? Wie kann ich zwei Algorithmen also vergleichen, wenn ich nicht konkrete Implementierungen nur vergleichen will, die ich laufen lassen kann und äh die die Zeit stoppen kann, sondern wenn ich die abstrakte Idee selbst vergleichen will.

2:57 Und die ähm die beste Möglichkeit, die wir dafür kennen, ist die Kosten nur als Approximation, um unendlich große Eingaben anzugucken. Damit kann man exakt extrahieren, was diese dieser Wachstumsteil ist und vollkommen ignorieren, was die konkrete Implementierung tut, was äh ähm konkrete Zeiten für einzelne Operationen angeht.

3:22 Also, sollten Asymptotik immer so verstehen in unserem Kontext als die Approximation von der Funktion. Im allgemein ist aber irgendeine Funktion. Für uns wird es eigentlich immer die die Kosten von dem Algorithmus sein, aber man kann natürlich die Definition ist mathematisch irgendeine Funktion, die approximieren wir für ganz große Eingabe, also um diesen Punkt n = unendlich. Den gibt's natürlich nicht als Zahl, aber das ist die ähm die Idee, die wir da immer verfolgen. Als Beispiel ist hier eine Funktion, die irgendwie einen langen Term hat. Da können Sie natürlich Zahlen einsetzen und schauen, wie die ungefähr wächst. Aber um die mit anderen Algorithmen zu vergleichen, ist es sehr unbequem. Dagegen bindet man eine sehr viel einfachere Funktion 2n², die sehr nah an dieser komplizierten Funktion liegt. Und insbesondere dieses Tildesymbol hat eine spezielle Bedeutung, die ich Ihnen gleich zeige. Ähm ist es hier eben eine asymptotische äh ganz tolle Approximation für die Funktion, die sind asymptotisch äquivalente in dem Fall Rechweise.

4:28 Also Ziel ist ähm die den Vergleich von Algorithmen möglich zu machen, ohne alle Details der Implementierung zu kennen. manchmal auch tatsächlich die Analyse dadurch erst möglich zu machen, indem sie soweit vereinfacht wird, dass wir überhaupt was konkretes sagen können. Da auch noch Beispiele. Unser Freeum Problem war sozusagen einfach genug, dass wir eine exakte Lösung hinbekommen haben, werden wir oft nicht schaffen. Und Ziel der Übung ist von unwichtigen Details zu abstrahieren, ähm damit wir wissen, worauf wir unseren Fokus richten. Also dann hier noch, bevor wir uns dann bis Mittwoch vertagen die Definition dieser asymptotischen Approximation.

5:11 Die einfachste und präziseste ist diese Tilde, die ich gerade schon verwendet hatte. Asymptotisch äquivalent sind diese zwei Funktionen, wenn ihr Quotient gegen ein konvergiert. Also hier in dem Beispiel ähm sehen Sie vielleicht diese anderen Terme, die da stehen, die sind deutlich kleiner als das n Quadrat, zumindest intuitiv. äh noch präziser fassen und dann habe ich hier vorne diesen einen Term, das so der typische Fall für eine asymptotische Äquivalenz. Das ist die einfachste Version. Die ist manchmal zu streng, manchmal kriegt man das nicht bewiesen. Da gibt's so eine schwammigere Version, das die großation und die ähm die am häufigsten bequemste Definition ist wieder über einen Kootienten von den Funktionen. Bei uns immer ähm mit Betragstrichen, insbesondere für Algorithmen, Kosten, die werden in der Regel positiv sein, dann ist es eh irrelevant. Ähm, manchmal macht's macht's auch Sinn, ähm negative Funktion zu betrachten, also immer mit Betragsstrichen. Ansonsten ist es auch wieder der gleiche Kozient der Funktion und der soll jetzt beschränkt sein.

6:21 Sprich, der haut nicht Richtungen endlich ab. Der ist kleiner als irgendeine obere Schranke. Er darf gegen null gehen, alles egal. Er darf auch schwanken. Er muss nicht konvergieren. Okay. Und wenn Sie das, wenn Ihnen das zu schwammig ist, dann können Sie das ersetzen durch der Limus Superior ist kleiner als unendlich. Wenn sie das verwirrend finden und den Limus Superior irgendwie mit dem Bild auch nicht intuitiver finden, dann bleiben sie bei dem. Das ist das gleiche. Varianten davon. Ähm, kommen vielleicht gleich dazu. Lassen Sie nämlich erst das Bild zeigen. Die die wichtige intuitive Version, die Sie im Kopf haben müssen, nach der Sie aber keine Beweise führen dürfen, weil wir dafür die Definition brauchen. Aber die Idee, die Sie im Kopf haben sollten für froß O von G ist F ist kleiner als G. Zumindest wenn ich konstante Faktoren ignoriere und endlich viele n abschneide. Also f von n ist kleiner als c* g von n für irgendeine konstante Zahl g c und eventuell erst ab einem Wert n0.

7:33 Okay, das ist was groß O besagt. Das ist eine obere Schranke. Schön, dass es auf Deutsch zusammenfasst mit den O für obere Schranke. Aber es ist keine normale obere Schranke im Sinne von einfach kleiner gleich, sondern immer mit diesen zwei Einschränkungen, die sind wichtig.

7:51 Okay, formale Definition eben über diesen Quotienten. Dann gibt's umgekehrt, wenn ich was zu einer oberen Schranke sagen kann, dann möchte ich manchmal auch untere Schranken haben. Das ist das Omega. Kein schöne keine schöne Eselsbrücke dafür. Vielleicht fällt Ihnen eine ein. Äh vielleicht sehen die Balken unten aus wie so eine untere Schranke vom Omega. Äh ist einfach das Umgekehrte. Wenn F groß Omega von G ist, also F ist größer als G, dann ist eben G kleiner als F. Ist auch einfach so definiert. Und thata, das kam ja vorhin schon vor. Teta ist dann eine obere und untere Schranke zusammen, sprich F ist in groß von G und F ist auch in Omega von G. Das klingt jetzt so, als müssten dann ja F und G im wesentlichen gleich sein, aber sie denken wieder dran, wir haben diese zwei Einschränkungen, das ist richtig. F ist th von G. heißt so ungefähr f = g, aber eben nur wenn man konstante Faktoren ignoriert und wenn man äh ab einem bestimmten großen n schaut.

8:58 Okay, dann gibt's noch die ab und zu verwendeten kleineren Varianten, die kleinen Buchstaben, klein O und klein Omega. Wenn das hier, wenn das groß sowas wie kleiner gleich ist, dann ist das kleino sowas wie echt kleiner. Aber aufpassen, es ist nicht formal einfach echt kleiner. Es ist viel viel stärker, nämlich der Kootient muss gegen null konvergieren. Das heißt, also dieses G ist deut wächst einfach deutlich schneller als das F. echt kleiner ist viel schwächer.

9:35 Okay, der große Vorteil von diesen Definitionen, die sie natürlich in genau der Form auf dem Cheat Sheet finden hier auf der linken Seite. Der Vorteil dieser Definition ist, dass alle damit anfangen, dass ich f dur g teile und mal gucke, was passiert, wenn das n größer wird. Also, machen wir ein kleines Beispiel dazu noch und dann ähm diesen diesen kleinen Punkt da unten, den führe ich nächstes Mal noch mal aus. Machen wir ein kleines Beispiel. Hier sind zwei Funktionen f und G. Oft werden sie gefragt werden, hier sind zwei Funktionen, gilt folgende asymptotische Relation zwischen den beiden ist f in groß O von G. Aber realistischer ist eigentlich, dass wir zwei Funktionen haben und gar nicht wissen, wie die sich zueinander verhalten. Wir wollen das erfahren. Dann mache ich eben auch das gleiche. Ich nehme den Kozienten f [räuspern] durch g von n und schaue mal, was passiert, wenn n groß wird. Und hier setze ich halt einfach mal ein.

10:42 Jetzt müssen wir richtig einsetzen, damit es auch stimmt. Dann kann ich diesen äh diese Summe aufteilen. Das ist also 3 + 2n². Da kann man kürzen, ne? Also 2 ge n. Ich hoffe, ich habe es nicht zu viele Schritte auf einmal gemacht. Also ich ich spalte die Summe auf, habe ich 3 n hoch 3 dur n hoch 3. N hoch 3 gekürzt bleibt nur die 3. 2n² dur n hoch 3 ist 2 geil dur n, nachdem ich gekürzt habe. Und jetzt sieht man der Grenzwert von diesem Quotienten.

11:31 Das ist der Grenzwert davon. Wir hatten uns schon überzeugt, dass 1 ge n gegen 0 konvergiert. 2 ge n konvergiert auch gegen 0. Das heißt, der Grenzwert davon ist 3. Der Teil hier, der geht gegen 0.

11:46 Was heißt es nun? Gehen wir unseren Definition zurück. Ich habe den Quotienten gebildet. Der Grenzwert ist nicht eins. Also das hier gilt nicht. Also leider ist F nicht tilde von G, aber 3 ist schon beschränkt. Das heißt F ist groß Ohr von G. Und ich kann auch weitermachen äh auch mein Omega gild, denn das ähm kann ich auch umdrehen. Also F von N ist groß O von G von N.

12:32 Und für das Omega muss ich die zwei Funktionen tauschen. Das heißt, ich betrachte den Kehrwert für gleich groß O von F von N. Wenn ich mich die frag, wenn ich mich das frage, dann muss ich jetzt ja g von n durch f von n teilen, aber ich habe für den Kehrwert ja schon den Grenzwert ausgerechnet. Der Grenzwert vom vom Kehrwert, wenn er denn eine endliche Zahl ist, ist dann halt der Kehrwert vom Grenzwert. Das konvergeiert also gegen ein Drittel. Das ist auch beschränkt. Das heißt, auch das hier gilt und damit gilt insbesondere auch f von nθ von g von n, denn ich habe sowohl groß O als auch groß om gezeigt.

13:21 Also, das war das eine. Daraus folgt nach Definition froß Omega von G von N. Na ja, und dann folgt das hier aus diesen beiden Teilen.

13:35 Das war ein einfaches Beispiel. Und vielleicht sehen Sie jetzt auch, warum ich vorhin sagte, der Limus Superior und all diese ähm Randfälle in der Definition, die die Definition alle abfangen soll, die tauchen oft gar nicht auf. Hier musste ich ganz einfach nur einen Grenzwert ausrechnen, den sie natürlich hinkriegen.