Laufzeitkomplexität von Algorithmen - die O-Notation

Gliederung

1.1 Historisches

• Es soll eine Funktion f in Abhängigkeit der Anzahl der Eingabewerte n gefunden werden, welche die Laufzeit eines Algorithmus' wiedergibt: f(n).
• Die angegebene Funktion f(n) soll unabhängig sein von systemspezifischen Details (tatsächlicher Zeitaufwand), daher ist von konstanten Faktoren c zu abstrahieren.
• Es soll eine Untersuchung des "ungünstigsten Falls" stattfinden und die Funktion f(n) soll mit einer Konstanten c als Faktor eine Asymptote bzw. Majorante zur tatsächlichen Laufzeit g(n) darstellen.

O(f(n)) ist die Menge aller der Funktionen g(n), für die es zwei Konstanten n₀ und c gibt, sodass für alle n n₀ gilt: 'g(n) c*f(n)'

g(n) könnte z.B. eine Laufzeit-Funktion eines Algorithmus' darstellen. Eindeutig zu sehen ist, dass g(n)<c*n4 ist, womit g(n)=O(n4) eine korrekte Aussage ist, jedoch sehr aufgerundet. Ebenfalls erkennbar ist, dass g(n)<c*n3 gilt und somit g(n)=O(n3) eine wahre Aussage darstellt. Dieser Term liegt schon näher an der kleinsten oberen Schranke. Der letzte Term stellt eine noch kleinere Majorante zu g(n) dar, ist jedoch nicht mehr komplett mittels O-Notation beschrieben. Will man eine exaktere Beschreibung der Laufzeit haben, so ist die Verwendung der O-Notation der falsche Weg. Wie schon erwähnt soll hierbei nur das allgemeine Wachstumsverhalten einer Laufzeit-Funktion gezeigt werden, jedoch nicht die exakte, von einem Rechner abhängige, Laufzeit.

• O(f(n)) ist eine Menge aller Funktionen g(n), für die gilt: g(n) c*f(n).
• g(n)=O(f(n)) bedeutet somit nichts anderes als: g(n) c*f(n).
• Wie schon mehrfach erwähnt: c*f(n)=O(f(n)) bildet eine obere Schranke der Laufzeit im ungünstigsten Fall, d.h. die tatsächliche Laufzeit g(n) wird für alle n>n₀ nie über c*f(n) liegen, wobei c eine rechner- und systemabhängige Konstante darstellt.
• Ist g(n)=O(f(n)) und gilt: g(n) h(n), so gilt auch: h(n)=O(f(n)).
• In umgekehrter Weise: ist g(n)=O(f(n)) und gilt: f(n) e(n), so gilt auch: g(n)=O(e(n)).

1.4 Interpretation

g(n) = a_k*n^k + a_k-1*n^k-1 + ... + a₀ (a_k+a_k-1+...+a₀)*n^k = c*n^k

• Sei g(n)=4n2-2n+2. g(n) ist ein Polynom 2-ten Grades, womit sich o.a. Aussage für Polynome anwenden lässt, wonach gilt: g(n)=O(n²). Dies lässt sich auch nochmals nachvollziehen: g(n) = 4n2-2n+2 (4-2+2)*n2 = 4*n2. Da c=4 eine Konstante ist, kann man die Definition der O-Notation anwenden: g(n) c*n², also g(n)=O(n²). Salopp ausgedrückt: "strebt die Anzahl der Eingabewerte n gegen unendlich, so wird der n²-Term dominant und alle anderen Terme sind zu vernachlässigen".
• Betrachten wir als zweites Beispiel den Sortieralgorithmus "Bubblesort". Da dies hier kein "Lehrpfad" für Sortieralgorithmen werden soll, gebe ich zur Veranschaulichung nur den Sourcecode des Algorithmus' in Form einer C-Funktion an:

  void bubblesort(int *a, int n){
      int hilf, i, j;
      for(i=n-1; i>0; --i)
  	for(j=0; j<i; ++j)
  	    if(a[j]>a[j+1]){
  		hilf=a[j]; a[j]=a[j+1]; a[j+1]=hilf;
  	    }
  }
  

  Schön zu sehen ist, dass zwei ineinander verschachtelte Schleifen ausgeführt werden. In diesem Fall gleicht eine Betrachtung des ungünstigsten Falls einer Betrachtung des Durchschnitts-Falls und auch des besten Falls, da die Anzahl der Schleifendurchläufe konstant ist und nicht vom zu sortierenden Eingabefeld abhängt. In der Mehrzahl der Fälle ist dies bei einer solchen Untersuchung allerdings nicht der Fall. Nach ein wenig Nachdenken sieht man, dass die innere Schleife pro Durchlauf der äußeren Schleife i-mal ausgeführt wird und die äußere Schleife (n-1)-mal durchläuft. i wird in der äußeren Schleife dekrementiert, womit sich für die innere Schleife ein Durchschnitt von "n/2" Durchläufen ermitteln lässt Zwei verschachtelte Schleifen multiplizieren sich (siehe auch 2.2), was heißt, dass die innere Schleife beim gesamten Durchlauf von Bubblesort "(n*(n-1))/2"-mal ausgeführt wird. In der inneren Schleife wird eine if-Abfrage ausgeführt. Im Falle des "worst case" wird sie genau so oft positiv getestet werden, wie die innere Schleife durchlaufen wird. Im Körper der Abfrage werden 3 Wertzuweisungen vorgenommen. Da angenommen werden soll, dass Abfragen und Wertzuweisungen eine konstante Zeit in Anspruch nehmen, besitzt diese if-Anweisung folgende Zeitkomplexität: h(n) c1+c2+c3=c. D.h. die komplette if-Anweisung nimmt eine konstante Zeit c in Anspruch, womit sich nach Definition der O-Notation wiederum sagen lässt: h(n) c*1, also: h(n)=O(1).
  Wird weiterhin in Betracht gezogen, dass h(n) genau "n*(n-1)/2"-mal ausgeführt wird, so lässt sich für die Laufzeit g(n) des gesamten Sortieralgorithmus' sagen:
  g(n) c*n*(n-1)/2 = c/2*n2 - c/2*n
  Hierbei handelt es sich um ein Polynom 2. Grades. Wie zuvor behandelt kann man deshalb über die Laufzeit g(n) von Bubblesort aussagen: g(n)=O(n2), anders ausgedrückt: "Bubblesort ist von quadratischer Komplexität".

• Die O-Notation gibt eine obere Schranke für die Laufzeit eines Algorithmus' im ungünstigsten Fall an.
• O(f(n)) beschreibt nicht eine Funktion, sondern eine ganze Menge von Funktionen.
• g(n)=O(f(n)) heißt eigentlich g(n) O(f(n)), das sollte man sich immer wieder klar machen. Aufgrund dessen dürfen die Seiten einer Gleichung in O-Notation auch nie vertauscht werden, eine solche Gleichung ist immer nur "von links nach rechts" gültig!
• Ein Polynom k-ten Grades besitzt die asymptotische Laufzeitkomplexität O(n^k).

1.5 Der O-Notation nicht blind vertrauen!

1. Die O-Notation gibt eine "obere Schranke" an, das heißt aber nicht, dass der Algorithmus auch jemals soviel Zeit benötigt, es heißt nur, dass garantiert NIE mehr Zeit benötigt wird. Vielleicht tritt der untersuchte ungünstigste Fall in der Praxis nie auf. Deshalb sollte man immer auch noch eine Betrachtung des durchschnittlichen und besten Falls in Erwägung ziehen.
2. Die systemabhängige Konstante c ist im Allgemeinen unbekannt, muss aber nicht unbedingt klein sein. Dies birgt ein erhebliches Risiko. Z.B. würde man natürlich einen Algorithmus, welcher n² Nanosekunden benötigt, einem solchen vorziehen, der n Jahrhunderte läuft, anhand der O-Notation könnte man diese Entscheidung allerdings nicht treffen, da eine lineare Komplexität besser zu sein scheint als eine quadratische. Hier ist also höchste Vorsicht geboten!
3. Die Konstante n₀, ab der für alle nn₀ gilt: g(n)c*f(n), ist ebenfalls unbekannt und muss genau wie c nicht unbedingt klein sein. So könnte n₀
1 Million betragen, in der Praxis könnten allerdings meist nur weniger Eingabedaten vorkommen. D.h. dass die Laufzeit des Algorithmus' über der mittels O-Notation angegebenen Schranke liegt und somit ein falsches Ergebnis vorliegt.
4. Schließlich ist die O-Notation eine Abschätzung der Laufzeit bei einer unendlichen Eingabemenge. Da jedoch keine Eingabe unendlich ist, sollte man bei der Wahl von Algorithmen die realistische Eingabelänge mit einbeziehen.

2.1 Wichtige Rechenregeln

• "c=O(1)", da von der Konstanten c abstrahiert werden soll
• "c*f(n)=O(f(n))", wie schon mehrfach besprochen
• "O(f(n))+O(f(n))=O(f(n))", was klar wird, da O(f(n))+O(f(n))=c1*f(n)+c2*f(n)=(c1+c2)*f(n)=c*f(n)=O(f(n))
• "O(O(f(n)))=O(f(n))" ist trivial erfüllt
• "g(n)=ak*nk+ak-1*nk-1+...+a0 = O(nk)", wie bereits im Beispiel unter 1.4 gezeigt wurde
• "O(f(n))*O(g(n))=O(f(n)*g(n))", was auch nahezu trivial erfüllt ist und hier sicher nicht weiter gezeigt werden muss
• "O(f(n))+O(g(n))=O(max{f(n),g(n)})"; hierbei gebe max{...} das Maximum der übergebenen Parameter zurück; die Gültigkeit der Rechenregel lässt sich wieder mithilfe der Definition der O-Schreibweise zeigen:
  O(f(n))+O(g(n)) = c1*f(n)+c2*g(n) 2*max{c1,c2}*(f(n)+g(n)) = c*(f(n)+g(n)) c*2*max{f(n),g(n)} = O(max{f(n),g(n)})
  Zum Verständnis der Ungleichungskette: es lässt sich sagen, dass die Summe von zwei Funktionen "f(n)+g(n)" (bzw. von zwei Konstanten "c₁+c₂") in jedem Fall kleiner ist als wenn die größere der beiden Funktionen zweimal ausgeführt wird, wodurch gilt: f(n)+g(n) 2*max{f(n),g(n)}

2.2 Laufzeit der Grundbausteine einer Programmiersprache

1. einfache Anweisung:
   Hierzu gehören beispielsweise Wertzuweisungen, Deklarationen bzw. Definitionen, einfache Arithmetik (+,-,*,/), Vergleiche (==,!=,<,>,<=,>=), Sprunganweisungen, Eingabe/Ausgabe, etc. . Die Laufzeit dieser Grundoperationen ist rechnerabhängig und soll als Konstante betrachtet werden, womit ihre asymptotische Laufzeitkomplexität O(1) beträgt.
2. Sequenz:
   Hierunter versteht man die Nacheinander-Ausführung mehrerer in 1. aufgeführter Grundoperationen oder aber die Nacheinander-Ausführung mehrerer von n abhängiger Algorithmen. Gesetzt den letzteren Fall, so stellt sich bei drei auszuführenden Algorithmen folgendes Bild dar: "alg1; alg2; alg3;": O(f(n))+O(g(n))+O(h(n)) = O(max{f(n),g(n),h(n)})" gemäß der in 2.1 aufgeführten Rechenregel der Addition von O-Kalkülen. Es sind also zunächst einmal die asymptotischen Komplexitäten der drei Algorithmen getrennt zu bestimmen und dann mittels Rechenregel zu vereinen.
3. Schleife
   Innerhalb einer Schleife werden meist die unter 1. gelisteten Basis-Operationen ausgeführt, womit der Schleifenkörper in konstanter Zeit durchlaufen wird. Bei n Durchläufen bedeutet dies: c*n=O(n). Eine Verallgemeinerung scheint sinnvoll, da der Schleifenkörper wiederum von n abhängig sein könnte, z.B. durch eine zweite innere Schleife oder weitere auszuführende Algorithmen. D.h. wenn der Schleifenkörper eine Zeitkomplexität von O(f(n)) hat und n-mal durchlaufen wird, so kann der gesamten Schleife O(n*f(n)) zugeordnet werden.
4. if-else-Anweisung:
   Bei positiv getesteter if-Bedingung werde alg₁ ausgeführt, sagen wir mit O(f(n)). Bei negativem Test hingegen soll alg₂ durchlaufen werden mit O(g(n)). Da mit der O-Notation der "worst case" betrachtet werden soll, ist klar, dass sich die Zeitkomplexität nach dem Algorithmus richtet, welcher von höherer Ordnung ist als der andere, da die Ausführung dessen genau diesen ungünstigsten Fall darstellt. Daher gilt für die if-else-Anweisung mit alg₁=O(f(n)) und alg₂=O(g(n)): O(max{f(n),g(n)})

//...
for(i=0; i<n; i++)
    for(j=0;j<n; j++)
	if(test)
	    bubblesort(a[i][j], n);
	else{
	    perror("Fatal error\n");
	    continue;
	}
//...

2.3 Typische Zeitkomplexitäten

• logarithmische Komplexität: O(log(n)); kommt z.B. bei der "binären Suche" vor sowie bei allen "square-and-multiply"-Verfahren; diese Komplexität ist sehr günstig, da die Laufzeit noch nicht einmal linear wächst, beispielsweise kommt es durch Quadrieren von n gerade einmal zu einer Verdopplung der Laufzeit
• lineare Komplexität: O(n); z.B. bei der Suche in einem unsortierten Feld; diese Komplexität sollte das primäre Ziel eines Algorithmenentwurfs sein, ist aber nur selten erreichbar
• n*log(n)-Komplexität: O(n*log(n)); die Laufzeit einiger der schnellsten Sortieralgorithmen wird dadurch charakterisiert (z.B. Mergesort); ist noch sehr günstig, wenn auch nicht mehr linear
• quadratische Komplexität: O(n²); in der Praxis charakterisierend für den Bubblesort-Algorithmus oder z.B. die Multiplikation einer Matrix mit einem Vektor; ist nicht mehr so günstig, da eine Verdopplung der Eingabedaten eine Vervierfachung der Laufzeit nach sich zieht, jedoch immernoch vertretbar
• kubische Komplexität: O(n³); z.B. bei der Multiplikation zweier Matrizen; ist noch ungünstiger
• exponentielle Komplexität: O(cⁿ); katastrophal schon für kleine n
• gemäß Fakultätsfunktion wachsende Komplexität: O(n!); katastrophal schon für kleine n
• superexponentielle Komplexität: O(nⁿ); katastrophal schon für kleine n
• hyperexponentielle Komplexität: O(n^{c₁c₂..c_n}); katastrophal schon für kleine n

2.4 Schlussbemerkungen

(c) 2004 by RTC, www.linux-related.de
Dieses Dokument unterliegt der GNU Free Documentation License