Video 5-3: Asymptotische Vergleiche

0:03 Es geht in diesem Kapitel jetzt nicht noch mal darum, wieder irgendwelche Grenzwerte zu berechnen, sondern es geht viel mehr um die Frage, warum Asymptotiken in der Algorithmik so zentral sind, nicht nur aus diesem praktischen äh Gesichtspunkt raus kosten kompakt zu beschreiben, sondern es gibt einen einen subtileren Punkt, auf den möchte ich Sie noch mal hinweisen. Hatten wir schon. Ja, es kommt drauf an, was wir wollen. Für die Algorithmik ist in der Regel das Ziel beliebig große Eingaben oder sogar der Grenzwert für n gegen unendlich diesen Fall gut zu machen. Also uns interessieren nur die schnellsten Züge, fast egal davon, wie lange wir brauchen, um anzufahren. Warum ist das der übliche Referenzpunkt? Ähm insbesondere macht es ja gar keinen Sinn. Also keine Eingabe ist ihr unendlich. warum äh überhaupt diesen Teil angucken.

0:58 Einerseits die pragmatische Variante ist, das ist in der Regel, wenn ich zwei Algorithmen vergleiche und ich habe die sozusagen die Endgeschwindigkeit, die ich vergleiche, dann ist das meistens auch die richtige Antwort für endliche n, einfach weil wir über so viele Größenordnungen hinweg arbeiten, dass das Wachstum, also Geschwindigkeit ist ein bisschen, ich verlasse mal die Metapher, was wir eigentlich haben, ist ja ein eine Wachstumsrate der Kosten und die kann ja mehr als eine Konstante te Geschwindigkeit sein. Ähm die Wachstumsrate der Kosten ist das, was über so große Anzahlen von Größenordnungen einfach einen viel größeren Einfluss hat, als sagen wir das Anfahren am Anfang oder die Konstanten. Und deswegen sehen Sie an das an das Brückenbeispiel ist aus pragmatischer Sicht der Fokus auf große Eingaben fast immer die richtige Wahl.

1:56 Deswegen Standardvorgehende Algorithmik ist auf die auf die Tetterklasse der Worstcase Laufzeit zu schauen, also insbesondere das Wachstum die Wachstumsrate der Kosten und Tetakklasse bedeutet auch noch, dass uns der konstante Faktor der Kosten erstmal nicht so sehr interessiert wie das die Wachstumsrate. Und erst im zweiten Schritt, wenn wir mehrere Algorithmen haben, die vielleicht in Frage kommen, schauen wir auch da noch genauer hin. Aber für ergrückenen Datenstrukturen ist im Wesentlichen das der Punkt oder das Präzisionslevel, an dem wir uns begnügen wollen. Es gibt auch noch einen zweiten ähm Grund, man kann das präziser machen, kennen Sie auch schon. Es gibt noch einen zweiten fundamentaleren Grund, warum wir eigentlich diesen Grenzwert für endgegen und endlich angucken müssen, wenn wir diese Universal Truths äh festhalten wollen. Für jede feste Eingabegröße kann ich immer schummeln im folgenden Sinn. Es gibt für ein festes für eine feste Eingabegröße, wenn Sie nicht seltsame Definitionen von Eingabegröße anlegen. Ähm wir wollen eigentlich immer eine Eingabegröße so wählen, dass dieses hier gilt, dass ich nur endlich viele verschiedene Eingaben habe für eine feste Größe. Und dann kann ich, wenn das man, wenn das das einzige die einzige Größe ist, die mich interessiert, alle Lösungen vorab berechnen und einen langen Spaghettiode bauen. Falls das die Eingabe ist, gibt diese zurück. Falls das die Eingabe ist, gibt das zurück. Das klingt jetzt nach einer langen Ifkaskade, die vielleicht langsam wäre. Wir werden aber noch sehen, da gibt's Datenstrukturen, die das besser machen. Also im Grunde kann ich äh mit einer mit einer Lösung alles vorab berechnen, dieses algorithmische Problem erschlagen.

3:41 Und es ist auch fast klar, dass kein Algorithmus, der das Problem wirklich löst, also von Grund auf die Lösung jedes Mal neu berechnet, da irgendwie mithalten kann.

3:51 Gleichzeitig ist aber aus praktischer Sicht das völliger Quatsch. Vielleicht gibt's 10 Millionen dieser Lösung, das ging ja noch. Vielleicht sind es ja 10 Trillionen. Also, wir haben gar nicht den Platz in dem Programm, um diese Lösung alle zu speichern, aber rein theoretisch gibt es immer diesen bestmöglichen Algorithmus, der dieses Problem dann löst für ein festes N und wir werden den nicht wegdefinieren können. Das heißt, für die Universal Truts, was ist der beste Algorithmus? Da gewinnt immer dieser Quatsch. Und ich möchte betonen, der ist wirklich in aller Regel Quatsch. Wenn ich eine halbwegs große Eingabe habe, gibt's zu viele Optionen für Eingaben, als dass ich die alle vorab berechnen kann. Klammer auf. Manchmal ist es eine ganz coole Idee für kleine Teilprobleme, aber das ist ein Randfall und nicht das Allgemeine Klammer zu. Wir haben also dann dieses dieses äh Problem, den besten Algorithmus zu finden hat Absurdum geführt, weil es immer diesen Schummelalgorithmus gibt.

4:53 Und das bedeutet insbesondere eine große Errungenschaft der Informatik, auf der ich noch bei weitem nicht genug ähm rumgeritten bin in dieser Vorlesung. Äh, eine große Errungenschaft sind Unmöglichkeitsergebnisse. Also mathematische Theoreme, die sagen, dieses algorithmische Problem kann man nie schneller lösen als diese und jene Laufzeit. Wir werden ein Beispiel fürs Sortieren sehen, wo das relativ leicht zu zeigen ist und trotzdem sehr aussagekräftig. Und es gibt dann in der Algorithmenforschung noch jede Menge anderer solcher Ergebnisse und die sind extrem stark im besondere im Vergleich mit anderen Ingenieurswissenschaften. Also, ich versuche mal den Vergleich ähm mit einem Verbrennungsmotor. Was wäre eine untere Grenze oder eine Schranke? Wie gut kann ein Verbrennungsmotor sein, was den den Wirkungsgrad angeht? Also maximal kann er die gesamte Energie vom Brennstoff in Bewegung umsetzen. Äh ich glaube übliche Verbrennungsmotoren sind so ein richtig guter ist bei 40%. Das allermeiste geht eben in Werbe in Wärme, Abgaswärme, Reibungsenergie verloren. Aber ist diese 40% jetzt magisch oder sind wir nur zu doof, eine bessere Konstruktion zu bauen? Unklar.

6:07 Das einzige, was wir haben, ist der Energieerhaltungssatz oder das auf erstem Level, das einzige, was ich kenne ist der Energieerhaltungssatz. der sagt mehr als 100 % geht nicht. S wir weit weg von den 40 50% im allerschlimmsten, im allerkrassesten Fall, die wir erreichen. In der Algorithmik oft viel viel besser. Die unteren Schranken sind so gut, dass wir die fast erreichen und keine Lücke mehr bleibt, sodass wir Algorithmen haben, die bestmöglich sind. All diese schönen Dinge, die ich ihnen jetzt hier beschrieben habe, die ähm gehen sofort kaputt, wenn man nur endliche N anschaut, weil es immer diesen Schummelalgorithmus gibt. Der macht also jegliche Ergebnisse solche Art unmöglich. Unmöglichkeitsergebnisse werden unmöglich. Na ja, deshalb wollen wir das nicht. Und die einzige aus der einzige Ausweg ist dann zu sagen, Algorithmen müssen für beliebig große Eingaben funktionieren oder wir vergleichen Algorithmen für den Grenzwert für n gegen unendlich für ihre Kosten, das Wachstum der Kosten, wenn die Eingabegröße immer größer wird.

7:13 Und insbesondere handeln wir uns damit soforten asymptotische Aussage ein, wann immer wir Algorithmen sinnvoll vergleichen wollen auf einem theoretisch fundierten, die zeit überdauernden Universal Truth Level.