Video 6-4: Typische Wachstumsraten

0:01 Im nächsten Abschnitt ein kleiner Überblick über die üblichen Wachstumsraten von Laufzeiten, die man so findet. Die sind natürlich nicht ganz vollständig, aber das sind die, die einem oft begegnen und für die es sich auch lohnt, einen eigenen Namen zu prägen, weil man dann relativ schnell einordnen kann, ungefähr in welcher Größenordnung wir uns bewegen.

0:23 Ähm in den äh Cwick Rainfolien heißt es Order of Growth, wenn Sie die Tetaklasse der des Wachstums meinen. Also für uns ist Order of Growth einfach die Thetasse Eine der wenigen Stellen, wo ich mit ähm dem Buch oder diesen Folien auch nicht ganz einverstanden bin. Ähm sie sagen hier, die Definition ist, dass eine Funktion f asymptotisch äquivalent ist zu einer anderen Funktion mal einem Faktor C in der Konstanten, die uns hier nicht weiter interessiert. Und dann ist also die diese Wachstumsrate von f ist dann g. Aber unser ist ein bisschen allgemeiner. Es muss nicht unbedingt eine feste Konstante geben, sodass dieses Tilde gilt, dieses asymptotische Äquivalenz, das ein bisschen strenger, also sind da ein bisschen ähm restriktiver und äh Klasse ist an der Stelle, glaube ich, die die schönere Formalisierung, aber das ähm das nur am Rande, also sie können sich im Wesentlichen darauf zurückziehen. Was wir in diesem in diesem Abschnitt meinen, ist wie können Funktionen wachsen und die Konstanten lassen wir dabei unter den Tisch fallen.

1:51 Ähm, warum diese Konstanten oft ignoriert werden, selbst die führende Konstante liegt daran, dass wenn man echte Laufzeiten betrachtet, ein konstanter Faktor immer von der Maschine und Details des Systems abhängen. Also, ich werde selten umhinkommen mit einer groben Überschlagsrechnung, wie wir das bei Freeam mal gemacht haben, präzise die Sekunden vorher zu sagen, die was auf einer unbekannten Maschine braucht. Was ich gut also theoretisch analysieren kann, ist diese Wachstumsrate oder inem abstrakten Kostenmaß zählen, wie oft werden z.B. Array Zugriffe ausgeführt und dann macht es auch Sinn, die Konstante zu behalten. Äh es hat sich in der Informatik oft äh eingebürgert, dass man alle Konstanten ignoriert, weil am Ende für echte Laufzeit ja sowieso die Konstanten von der Maschine abhängen. Das ist so ein bisschen das Kind mit dem Bade ausgeschüttet. Manchmal kann man ohne Probleme genauer sagen, was passiert.

2:51 Aber das ist, wo das herkommt. Äh, wenn man die diese Tetaklasse von einem Stück Code kennt, dann kann man mit ein zwei Messungen auf einer Maschine die Konstante, die da äh vorne dran dann fehlt, bestimmen oder schätzen und davon dann Laufzeitvorhersagen machen.

3:14 Welche Arten von Wachstümern können wir bei typischen Algorithmen also erwarten? Äh hier sind mal ein paar aufgemalt, die mehr oder minder öfter vorkommen. Ähm was dann besser oder schlechter ist. Also eine Option ist konstant, hängt gar nicht von der Eingabegröße ab. Das ist natürlich wunderbar. Dann kostet die der Algorithmus immer gleich viel. Logarithmisch ist die nächst kleinere. Ähm ich sollte vielleicht hier denn dick unterstreichen, dass das Bild zur Illustration hier ein Log Plot ist. Das heißt, einerseits, wir haben hier einen relativ großen Bereich auf den beiden Achsen abgedeckt. Deshalb sieht man auch relativ krass diese Unterschiede zwischen den Funktionen. Ähm und zweitens ist dadurch natürlich ähm das Bild hier fast so, als wären alles diese Funktionen Konstanten. Wenn man genau hinguckt, ist das natürlich nicht so. Also der Logarithmus ist so leicht gebogen und die Exponentialfunktion ist auch auf einem logot noch eine exponentielles Wachstum, aber da die hier schon fast senkrecht steht, sieht man da nicht mehr viel. Was aber das Bild glaube ich sehr eindrücklich zeigt, ist in welcher Reihenfolge diese Wachstüme angeordnet sind. eben von langsam bis gar nicht wachsen bis hin zu exponentiell wachsen.

4:32 Und äh das sind auch, wenn man die Konstanten vorne dran auf eins setzt, ganz klare eine Rangfolge von wie gut oder wie schlecht ist eine Laufzeit.

4:46 Woher können die kommen diese Laufzeiten? Also hier noch mal die gleichen Tlassen. Sie sollten sich hier bei allem, wenn Order of Growth steht, meinen wir immer theta Klasse davon, also theta von 1, thata von log n und so weiter. Ja, in der Tabelle sind so ein paar typische Beispiele, jetzt mache ich es noch fertig. angegeben, welche Arten von Coach Nipseln dafür verantwortlich sein können, dass man so einen Laufzeitverhalten bekommt. Konstanten hat man schon, das sind die einfachen Anweisungen, die einfach nur einmal ablaufen und keinerlei Wiederholung enthalten. Ein logarithmisches Verhalten, wenn wir gleich noch ein Beispiel sehen, äh bekommt man insbesondere aus dem Master Theorem, aus dem Fall aus dem mittleren Fall. Ähm und die einfachste Variante ist, dass man etwas wiederholt und dabei jedes Mal die Größe halbiert. Logarithmus ist, wie oft muss ich was verdoppeln, bis ich bei n bin? Das heißt, umgekehrt, wenn ich bei n starte, wie oft muss ich was halbieren, bis ich bei 1 bin? Ist auch Logarithmus.

5:51 Ähm, linear hat man schon viele Beispiele Zählschleife, ebenso quadratisch und kubisch sind Zellschleifen, die ineinander geschachtelt sind. Das ist der typischste Fall, was wir äh in den One Sum, Two Sum und Three Sum Beispielen schon gesehen hatten. Dann gibt's noch so Dinge dazwischen. Äh linearhitmisch ist so ein Kunstwort aus linear und logarithmisch. Also das ist äh vielleicht nicht in jedem Lexikon zu finden und nicht in jedem Wörterbuch zu finden. Ähm in der Algorithmik verwendet man es ganz gern, weil es doch klar ist, was gemeint ist. Selbst wenn das Wort vielleicht ein bisschen künstlich ist. Äh, das ist also ein Verhalten n log n. Da werden wir dann im nächsten Abschnitt hat ja schon nach Sortieralgorithmen gefragt äh reichlich Beispiele für sehen. Und das einzige, was wir noch nicht an Beispielen groß hatten, weil auch die Algorithmen, die solche Laufzeiten haben, relativ wenig hilfreich sind in der Praxis, ist exponentielles Wachstum.

6:54 Äh, das ist hier exponentiell kann mehr heißen als 2 hoch n. Die Konstante in der Basis macht einen Unterschied für die Thalasse. Also jede Zahl hier 3 hoch n ist anders als 2 hoch n. Noch schlimmer. Ähm das ist ja alles aber mit exponentiell jede Möglichkeit von Basis gemeint.

7:16 Das hat man im Wesentlichen dann, wenn man z.B. alle Teilmengen einer nelementigen Menge durchstreicht. Dann sind es ja für jedes Element habe ich die Option, das sind die aktuelle Teilmenge aufzunehmen oder rauszulassen. Das heißt, ich habe zwei hoch n Möglichkeiten insgesamt. Mit derartigen Algorithmen werden wir uns in dieser Vorlesung wenig beschäftigen, wie gesagt, weil die einfach so schnell so langsam werden, dass man selten viel damit anfangen kann. Äh können Sie dann den fortgeschrittenen Veranstaltungen mehr zu lernen, äh wo man versucht clever mit denen umzugehen bzw. sie auch Eingaben anzuwenden, wo dann der exponentielle Teil klein ist. Ähm, ein Fokus noch einmal auf die letzte Spalte. Das ist das, was Sie im Experiment oft gut beobachten können, nämlich die äh der das Verhältnis von der Laufzeit für 2n geil durch der Laufzeit für n. Das ist diese Doubling Hypothesis, die wir letztes Mal hatten. Äh und für die verschiedenen Wachstüme sehen Sie da ganz gut, dass man mit einer Zahl viele der Zeilen unterscheiden kann.

8:21 Man kann logarithmische Faktoren, also zwischen konstant und logarithmisch oder zwischen linear und linearhittmisch kann man nicht unterscheiden damit. Ja, sie sehen hier, das ist ungefähr eins. In Experimenten sind die halt alle immer nur ungefähr diese das ist immer nur der Grenzwert. Deswegen ist das immer so ein bisschen ähm mit Vorsicht zu genießen. Ich kann zwischen diesen beiden eigentlich nicht unterscheiden.

8:54 Also, ich kann erkennen, ob die das Verhältnis ein oder zwei ist oder was dazwischen, aber diese logarithmischen Faktoren, dafür musste man dann einen anderen Test machen, z.B.

9:04 durch Logarithmus teilen und sich dann das ja Ergebnis anstellen statt diesen äh Verdopplungstest zu machen. Also im Grunde sollten Sie die Folie insofern im Kopf behalten, dass sie von dieser letzten Spalte rückwärts gehen können und dass sie die Namen dieser Tetklassen im Kopf behalten sollten, weil die so oft vorkommen, dass ich wahrscheinlich die Begriffe verwende, ohne jedes Mal dazu zu sagen, was die Tetakklasse ist. Die Erwartung ist also, dass sie das mit der Zeit äh kennen. Die meisten sind ja auch, glaube ich, selbsterklärend.

9:47 So viel dazu. Ich habe noch einen netten Fund über wie äh kompetent groß O in der Praxis manchmal verwendet wird. Ist ein Artikel aus Communications of the ACM. ACM ist sowas wie die amerikanische GI. Kennt jemand GI, die Gesellschaft für Informatik? Äh, das ist so die ähm Learn Society der Informatiker in Deutschland, also die die ähm Expertenvereinigung der Verein der deutschen Informatiker, Gesellschaft für Informatik. ACM ist die amerikanische Version davon und auch Dachorganisation für viele Dinge global. äh die Association for Computing Machinery äh klingt so ein bisschen altmodisch und das ist halt einfach äh auch schon ein Weilchen her, dass der Name geprägt wurde. Und Communications of the ACM ist so die ähm die soll wir sagen Vereinszeitschrift, die aber schon etwas mehr Renom hat als irgend so ein äh Blättchen vom Turnverein. äh da werden regelmäßig auch bekannte Artikel veröffentlicht und da gab es eben einen zu äh der Infrastruktur, die Meta so bereithält in ihren Datencentern.

11:00 Da gab's ganz viele kuriose Vorkommen von Groß O, die natürlich alle Quatsch sind, weil groß O von 100.000 ist ja immer noch ein oder groß O von 1. Ähm in dem Fall ist vermutlich gemeint ungefähr 100.000, 1000, aber machen sie das nicht. Das ist äh nicht die professionelle Variante, wie man groß verwendet. Äh definitiv nicht in der Algorithmik. Allen, den ich es gezeigt habe, haben äh mindestens geschmunzelt oder die die Augen gerollt. Aber so ist es. Ich habe ihn ja versprochen, dass groß O viel verwendet wird. Ja.