Vorlesung Informatik 2 - Teil B: Theorie
1.2 Komplexität
Wie betrachten die lineare Suche in einer Menge von N Elementen aus dem letzten Abschnitt und versuchen, den Rechenaufwand abzuschätzen.
Der Algorithmus besteht im Wesentlichen aus einer Schleife über die Elemente der gesuchten Menge. Wird das Element nicht gefunden, läuft die Schleife über alle Elemente, wenn das Element gefunden wird, bricht die Schleife ab. Im Mittel wird die Länge der Schleife bei N/2 liegen.
Der Aufwand ist also proportional zu der Menge der Daten, d.h. wenn sich N verdoppelt, verdoppelt sich auch der Aufwand.
Es macht keinen Sinn, den Aufwand als Zeit oder Anzahl Operationen anzugeben - die Zeit hängt ja stark von der verwendeten Hardware ab. Entscheidend ist vielmehr das funktionale Verhalten, also in diesem Fall die lineare Abhängigkeit des Aufwandes von der Datenmenge N.
Das Verhalten eines Algorithmus im Verhältnis der Datenmenge nennt man Komplexität, sie erlaubt eine Aufwandsabschätzung für einen Algorithmus. Um das Verhalten zu charakterisieren, gibt man eine Funktion an, welche eine obere Schranke für das Wachstum des Aufwandes in Abhängigkeit von N angibt.
Für die lineare Suche haben wir für den Aufwand die Funktion f(N)=0,5 N gefunden, also eine lineare Beziehung. Der Faktor 0,5 ist in diesem Zusammenhang allerdings uninteressant, wichtig ist nur, dass ein linearer Zusammenhang besteht.
Für die Komplexität hat sich die sogenannte O-Notation etabliert, die auch nach dem Mathematiker Edmund Landau als Landau-Notation bezeichnet wird. Das lineares Verhalten wird in dieser Notation als O(N) bezeichnet, man sagt die lineare Suche hat die Komplexität O(N).
Da der Faktor vor der Funktion irrelevant ist, wird er weggelassen, bzw. es gilt allgemein folgender Satz:
Zwei Komplexitäten, die sich nur um einen Faktor k unterscheiden, sind gleich, also O(f(N))=O(k f(N)).
In der Praxis sind nur sehr wenige Komplexitäten von Bedeutung:
- O(1) - konstant, d.h. der Aufwand hängt nicht von der Datenmenge ab.
- O(log N) - logarithmisch
- O(N) - linear
- O(N log N) - superlinear
- O(N2) - quadratisch
- O(N3) - kubisch
- O(Nk) - polynominal
- O(2N) - exponentiell
Wobei die beiden letzten bei größeren Datenmengen schnell dazu führen, dass ein Problem praktisch nicht lösbar ist.
Mathematisch beschreibt man das Konzept der Komplexität folgendermaßen:
\( f(N)=O(g(N)) \Leftrightarrow \exists \ c,N_0 \ \forall \ N \geq N_0 : f(N) \leq c \cdot g(N) \)
Kurz gesagt: wenn die Funktion f(N) die Komplexität O(g(N)) hat, ist g(N) eine obere Schranke für das Wachstum von f(N).
Oft besteht ein Algorithmus aus mehreren Teilen, die sequentiell abgearbeitet werden. In diesem Fall wird nur der Teil mit der größten Komplexität berücksichtigt:
Die Komplexität eine Algorithmus ist gleich der größten Komplexität seiner Teilalgorithmen.