Zufallsbit

Viele meiner Suchanfragen lassen vermuten, dass einige Informatikstudenten im ersten Semester händeringend nach Beispielen suchen, wie man mit der O-Notation umgeht. Ich werde hier ein Beispiel durchrechnen, in der Hoffnung dass es jemandem hilft. Lasst doch ein Kommentar da wenn das der Fall ist ;)

Also, neben der informellen Beschreibung der O-Notation gibt es natürlich auch den streng formalen Weg. Zunächst nehme ich mir mal den Bubble-Sort heraus und kopiere den Pseudocode von Wikipedia:

prozedur bubbleSort( A : Liste sortierbarer Elemente ) definiert als:
  n := Länge( A ) - 1
  wiederhole
    vertauscht := falsch
    für jedes i in 0 bis n wiederhole:
      falls A[ i ] > A[ i + 1 ] dann
        vertausche( A[ i ], A[ i + 1 ] )
        vertauscht := wahr
      falls ende
    für ende
    n := n - 1
  während vertauscht
prozedur ende

Jetzt analysieren wir, wie man diesen Algorithmus bezüglich der O-Notation klassifizieren muss. Zunächst einigen wir uns darauf, dass wir nur Zuweisungen, Additionen und Vertauschungen (was ja auch nur Zuweisungen sind) als Rechenschritt zählen. Alles andere kostet natürlich auch Zeit, macht aber verhältnismäßig wenig aus.

Also los: Zeile zwei ist eine Zuweisung, das ist ein Rechenschritt. Alles was zwischen Zeile drei und  zwölf steht  wird wiederholt, und zwar so lange bis das Array sortiert ist. Wann ist das im schlimmsten Fall passiert? Natürlich wenn das Array umgekehrt sortiert ist. Denn dann muss das vorderste Element nach hinten und umgekehrt. Da Bubble-Sort immer nur direkte Nachbarn vertauscht, muss jedes Element also ganz durchgeschoben werden. Also weiter, das erste Element muss also ganz nach hinten, braucht dafür n Durchläufe der "für"-Schleife. Pro einen solchen Durchlauf brauchen wir einen Vergleich, eine Vertauschung und eine Zuweisung. Wir sind also im Moment bei . Dann wird noch das n heruntergezählt und dann wird die "wiederhole"-Schleife durchlaufen. Das passiert auch n-Mal in unserem worst-case.

Da bekommen wir also und damit . Gut, wie erwartet ist das eine quadratische Laufzeit, bleibt nur noch formal zu zeigen dass das auch wirklich ist. Dafür ist natürlich zunächst die formale Definition nötig, die sieht so aus:

Da steht also folgendes: Es gibt eine Funktion g, die schneller oder gleich schnell als unsere Funktion f wächst. Dazu multiplizieren wir noch eine Konstante c dran, die wir uns für den Beweis wählen können. Plastischer wirds erst, wenn ich das mal eben für das Beispiel durchführe.

Jetzt muss ich nur noch ein c und ein finden, für das die obige Gleichung gilt, dann gilt es auch für alle größeren n und der Beweis ist geführt. Dafür dividiere ich aber erst durch , dann wird es einfacher:

Ich wähle und c=5, die Gleichung ist erfüllt und es ist leicht zu sehen, dass sie auch erfüllt bleibt, wenn das n größer wird. Ab dem bleibt die Bubble-Sort Funktion also immer im -Bereich, Beweisende.

Ich hatte ja schon über die O-Notation gesprochen und schon angedeutet, dass wir nur im wesentlichen polynomielle und exponentielle Laufzeiten auseinander halten wollen. Die Grafik im betreffenden Post war ja schon ganz anschaulich, aber ich will es doch noch ein bisschen plastischer machen um auch die praktisch veranlagten zu überzeugen.

Ich habe ein paar Tests laufen lassen und habe einen kleinen, sinnlosen Algorithmus in Python geschrieben. Dieser füllt ein Array und macht nichts weiter außer ein paar überflüssigen Additionen. Für ein Array der Größe 100 braucht dieser Algorithmus ziemlich genau eine Sekunde CPU-Zeit. Natürlich interessiert uns dabei die absolute Zahl überhaupt nicht, mir ist klar dass C schneller wäre und es schnellere Prozessoren gäbe. Das ist sozusagen die Pointe des Ganzen: Uns ist völlig egal, ob es zwei oder hundert Sekunden sind, es geht darum ob es einen andere Algorithmus gibt, der bei gleichen Vorraussetzungen schneller ist. Genau deshalb benutzen wir Turingmaschinen, damit die Voraussetzungen gleich sind.

Aber ich schweife ab. Mein Algorithmus braucht also eine Sekunde für n=100. Das bedeutet für 100³ "Schritte" braucht mein Computer eine Sekunde. Erhöhen wir mal auf n=1000, da wären wir bei runden 17 Minuten für 1000³ Schritte. Das ist schon nicht mehr ganz wenig. Für n=10000 allerdings wären wir bereits bei guten 31000 Jahren. Das ist bereits utopisch für den realen Einsatz, aber wie siehts denn im Vergleich mit aus?

Für n=10 haben wir noch überschaubare 17 Sekunden, aber da hört es auch schon auf. Wir erinnern uns: beim Algorithmus brauchte mein Computer für n=100 eine Sekunde. Bei sind es 40196936841331475186983 Jahre. Und das für n=100, was für reale Anwendungen noch sehr wenig ist. Schon die Laufzeit für n=1000 wäre unvorstellbar groß.

Man zieht also die Grenze da, wo das n im Exponent steht. Das führt natürlich auch zu Ungenauigkeiten, so wäre in Ordnung, während exponentielles Wachstum hat, wobei es für alle praktischen Werte langsamer wächst als die erste Funktion. Trotzdem ist hier eben die Grenze, die nicht mehr ganz so an den Haaren herbei gezogen wirkt, wenn wir erstmal wissen, was NP genau ist. Im Moment jedoch müssen wir einfach mal akzeptieren dass polynomielle Laufzeit okay ist, während ein n im Exponent nicht okay ist.

Hier also der erste Beitrag mit Substanz, es geht um die O-Notation. Das werden wir brauchen um uns zu überlegen, was effektive Algorithmen sind und was nicht. Ein Algorithmus ist übrigens eine Abfolge von Schritten, um ein gegebenes Problem zu lösen. Es liegt natürlich nahe, einen Algorithmus in ein Computerprogramm zu verpacken, das ist aber nicht zwingend nötig für eine Laufzeitberechnung.

Womit wir schon beim Thema wären, denn Algorithmen lassen sich nicht exakt vergleichen, dafür gibt es einfach zu viele unbekannte Faktoren. Zum Beispiel ist eine Implementierung in C sicher schneller als in Ruby, es sei denn der Programmierer baut großen Mist. Vielleicht benutzt der eine Programmierer noch einen Pentium 3, während der nächste auf einem Athlon64 sitzt und deshalb besser mit großen Zahlen rechnen kann. Oder vielleicht implementiert die Standard-Library von Betriebssystem A die verkettete Liste etwas langsamer als System B. Kurz gesagt, diese ganzen Unwägbarkeiten müssen raus und man muss sich Zwecks Vergleichbarkeit auf das absolute Minimum eines Algorithmus beschränken. Das wäre eben die Beschreibung der nötigen Schritte pro Element. Formal braucht man auch immer eine Eingabe und Ausgabe dazu, bei der Ausgabe kann man sich aber oft auf "wahr" oder "falsch" beschränken, wie wir später sehen werden.

Ein Beispiel:
Problemstellung: Ich will möglichst betrunken werden.
Erwartete Ausgabe: "wahr" (Ziel erreicht) oder "falsch" (Bier leer)
Algorithmus:
- Aufstehen
- Zum Kühlschrank gehen
- Bier nehmen
- Zum Sessel gehen
- Setzen

Sagen wir, Schritt 1, 3 und 5 brauchen "eine Zeiteinheit", 2 und 4 brauchen jeweils drei. Pro Bier brauchen wir also neun Schritte, ganz unabhängig davon z.B. welche Biermarke wir haben. Um das Ziel des Algorithmus zu erreichen brauchen wir also ganz allgemein 9*n Schritte, wobei "n" die Anzahl Bier ist, bis man komplett dicht ist (und das variiert von Person zu Person, was hier die "Eingabe" wäre). Aber wie relevant ist die neun denn wirklich? Was, wenn wir einfach den Alkoholgehalt pro Flasche verdoppeln? Dann bräuchten wir nur noch 4,5*n Schritte. Man könnte auch weitere Laufzeitverbesserungen vornehmen indem man zwei Bier pro Lauf mitnimmt, dann wären wir bei Schritten. Es stellt sich heraus dass das "n" immer mit im Term steht, also müssen wir weiter abstrahieren und das "n" als Maßstab für die Güte des Algorithmus nehmen. Wir vergessen einfach den Faktor davor und sagen O(n) dazu. Das bedeutet dann soviel wie "der Algorithmus hat im Wesentlichen eine Laufzeit von n". n ist allgemein die Eingabelänge, üblicherweise ist das eine Array der Größe n oder ähnliches. Man muss sich das mal für sehr große n überlegen. Je größer das n wird, desto kleiner wird der Unterschied, den Faktoren ausmachen und umso größer wird der Einfluss des n.

Dazu auch ein Beispiel: Wir vergleichen und . Für n=5 braucht der erste Algorithmus 70 Schritte, der zweite 12,5. Man könnte auf die Idee kommen, doch den zweiten einzusetzen, aber schon bei n=100 haben wir 1020 bzw. 5000 Schritte. wächst eben sehr viel schneller als n, deshalb klassifiziert man den ersten Algorithmus als und den zweiten als . Wenn man das jetzt mathematischer formulieren würde, könnte man sehen, dass sogar , es zählt also nur der höchste Exponent, bzw. der Term, in dem n am schnellsten wächst.

Übrigens umfasst das "O" auch andere Laufzeiten, gibt damit sozusagen eine obere Schranke an. Wenn man O(n) schreibt, meint man "Der Algorithmus schafft das Problem in linearer Zeit, obwohl es vielleicht spezielle Eingabe gibt, wo er nach einem Schritt fertig ist." In jedem Fall aber braucht er nicht länger als Linearzeit. Wenn man eine genaue Aussage treffen will nimmt man und meint "Der Algorithmus braucht für jede Eingabe im wesentlichen Linearzeit".

Wichtige Laufzeiten sind z.B. ,,,, oder

Dabei bedeutet O(1) nicht, dass in jedem Fall nur ein Schritt nötig ist, es können auch 10000 Schritte nötig sein. In jedem Fall muss die Anzahl der Schritte konstant sein um O(1) genannt werden zu dürfen. Um ein Gefühl für das Wachstumsverhalten zu bekommen, hier zum Schluss nochmal ein Plot der Funktionen.

Hier sieht zugegebenermaßen der Plot für nicht besonders beeindruckend aus, aber wie schon erwähnt kommt es vor allem aufs Wachstumsverhalten an, und das betrachtet man in der Regel für große n.





Hier noch ein Plot, diesmal vs. . Und das sind nichteinmal besonders große n, sondern irgendetwas zwischen 60 und 70. Man stelle sich das mal für n>1000 vor. Und schaut euch mal dem Maßstab an der y-Achse an.

Fassen wir also zusammen: Um Algorithmen zu vergleichen abstrahiert man so viel wie möglich, lässt im wesentlichen alle nicht relevanten Terme weg und betrachtet nur den Teil des Algorithmus, der am schnellsten wächst. Und weil ihr bis hier durchgehalten habt, kommt hier der Clou: Eigentlich interessiert nur, ob das n im Exponent steht oder nicht. oder ? Egal, kommt aufs gleiche raus. Aber ? Böse! Warum das so ist, soll jetzt erstmal egal sein. Wichtig ist nur, dass es in der Praxis höchst wichtig ist ob man O(n) oder O(n*log(n)) hat, in der Theorie nicht.