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 $1+n*(1+1+1)$ . 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 $1+n*(n*(1+1+1)+1)$ und damit $3n^2+n+1$ . Gut, wie erwartet ist das eine quadratische Laufzeit, bleibt nur noch formal zu zeigen dass das auch wirklich $O(n^2)$ ist. Dafür ist natürlich zunächst die formale Definition nötig, die sieht so aus:

$\exists{c>0},n_0\forall{n\geq n_0}:f(n)\leq c\cdot g(n)$

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.

$f(n)\leq c\cdot g(n)$

$3n^2+n+1\leq c\cdot n^2$

Jetzt muss ich nur noch ein c und ein $n_0$ 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 $n^2$ , dann wird es einfacher:

$3+\frac{1}{n}+\frac{1}{n^2}\leq c$

Ich wähle $n_0=1$ 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 $n_0=1$ bleibt die Bubble-Sort Funktion also immer im $O(n^2)$ -Bereich, Beweisende.

O-Notation Beispiele Geschrieben von Turing in Geek-Zeug um 11:04
Kommentare (5) Trackbacks (0)

Tags für diesen Artikel: algorithmus, geek-zeug, informatik, komplexitÃ¤t, o-notation, sonstiges mathematisches, wachstum

Mittwoch, 4. April 2007

Die xkcd-Zahl

Ich bin ja ein bisschen Stolz, dass ich bei Google bereits zweiter beim Suchbegriff "P vs NP" bin. Trotzdem gehts jetzt erstmal um etwas anderes.

Im dritten Panel dieses wunderbaren Comics kommt eine Zahl vor, die der Autor selber gerne als "xkcd number" bezeichnet. Ich bin immer seltsam fasziniert von solchen relativ sinnlosen mathematischen Geschichten, deshalb will ich diese spezielle hier mal erwähnen.

Die xkcd-Zahl ist also folgende: A(g₆₄,g₆₄)

Die Funktion A(.,.) ist hierbei die Péter-Version der Ackermannfunktion, welche extrem schnell wächst. Sie führt sozusagen die Operationen Addition und Multiplikation fort. Während die Multiplikation nur die wiederholte Ausführung von Addition ist (3*a = a+a+a), ist das "höhere Level" der Multiplikation z.B. a³ = a*a*a. Was kommt danach? Keine Ahnung, aber die Ackermannfunktion macht genau das. A(4,4) wäre die "vierte Stufe der Operationen" mit der vier. Wie groß ist A(4,4)? Nun ja, ziemlich. A(4,4) kann ich schon nicht mehr ausdrücken, deshalb mache ich mal ein Beispiel mit A(2,4): Wollte man sie aufschreiben, müsste man einen Anzahl dicht bedruckter Seiten benutzen, die etwa 20000 Stellen hat. Versteht das richtig: Die Anzahl der Seiten hat 20000 Stellen, nicht die Zahl selber. Um die Anzahl der Seiten aufzuschreiben bräuchte man ebenfalls mehrere Seiten. Und das für A(2,4). Man kann sich vorstellen, dass alles was darüber kommt nicht mehr aussprechbar groß ist.

Was ist jetzt g₆₄? Wir kennen ja 3^3, das ist "3 zur dritten Potenz". Dann könnten wir 3^^3 sagen, das wäre 3^ (3 ^ 3), also 3^27, was schon ziemlich groß ist, irgendetwas mit 7 Billionen. Jetzt sagen wir, 3^^^3 wäre 3^^(3^^3), also 3 ^ (7625597484987 ^ 7625597484987). Ui, das wächst ja ziemlich schnell, schon diese letzte Zahl ist wahnsinnig viel größer als A(2,4). Selbst wenn man jedes Atom im Universum als Tinte benutzen könnte, man könnte diese Zahl nicht niederschreiben. Was ist aber jetzt Grahams Zahl? Das ist eben g₆₄ und sieht so aus: 3^^^...^^^3, mit 64 "^" zwischen den dreien. Und wir erinnern uns, bereits 3^^^3 war astronomisch groß.

Und jetzt zurück zur xkcd-Zahl. Da wird ja die Graham-Zahl in die Ackermannfunktion gefüttert, und da fehlen mir die Worte, wie groß diese Zahl ist. Zugegeben, komplett sinnlos ist sie auch, aber groß. Sehr groß.

Die xkcd-Zahl Geschrieben von Turing in Sonstiges um 08:45
Kommentar (1) Trackbacks (0)

Tags für diesen Artikel: sonstiges, wachstum, xkcd

Dienstag, 6. M�rz 2007

O-Notation

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 $(4.5/2)*n$ 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 $10*n + 20$ und $1/2*n^2$ . 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. $n^2$ wächst eben sehr viel schneller als n, deshalb klassifiziert man den ersten Algorithmus als $O(n)$ und den zweiten als $O(n^2)$ . Wenn man das jetzt mathematischer formulieren würde, könnte man sehen, dass sogar $n^2 + 7*n = O(n^2)$ , 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 $\Theta(n)$ und meint "Der Algorithmus braucht für jede Eingabe im wesentlichen Linearzeit".

Wichtige Laufzeiten sind z.B. $O(1)$ , $O(n)$ , $O(n^2)$ , $O(log(n))$ , $O(n*log(n))$ oder $O(2^n)$

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 $2^n$ 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 $2^n$ vs. $n^{10}$ . 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. $n^2$ oder $n^{100}$ ? Egal, kommt aufs gleiche raus. Aber ${0.1}^{n/100}$ ? 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.