Dipl. Phys.  Gerald  Kempfer
Gastdozent an der Berliner Hochschule für Technik

Wenn die Laufzeiten (und damit auch die Effizienz) von Algorithmen verglichen werden, reicht es nicht aus zu sagen, dass ein Algorithmus schneller ist als ein anderer. So wird z.B. das Bubblesort-Verfahren eine Datenmenge von 10 Datensätzen auf einem sehr schnellen Computer schneller sortiert haben als das Quicksort-Verfahren eine Datenmenge von 1 Million Datensätzen auf einem langsamen Computer. D.h. die tatsächliche Laufzeit hängt von mehr Faktoren als nur vom Algorithmus und der Taktfrequenz des Computers ab.

Um nun Algorithmen besser vergleichen zu können, wurde der Begriff der Komplexität eingeführt. Die Komplexität eines Algorithmus ist die Abschätzung des Aufwandes seiner Realisierung auf einem Computer. Dabei bedeutet die Abschätzung des Aufwandes, wie sich der Aufwand verändert, wenn sich die Menge der Daten verdoppelt. Der Laufzeitaufwand z.B. wird durch Zählen von der Anzahl von Durchläufen (meistens Schleifendurchläufen) ermittelt. Dabei werden Operationen, die nicht von der Anzahl der Datenmenge abhängen, nicht mitgezählt, da sich diese bei Verdopplung der Datenmenge nicht ändern.

Bei der Komplexität wird im wesentlichen zwischen drei verschiedenen Arten unterschieden:

Die Laufzeit-Komplexität ist die Abschätzung der Computerrechenzeit (Laufzeit des Programms) und ist die Komplexität, die am häufigsten angegeben wird. So wird auch hier im folgenden die Laufzeit-Komplexität betrachtet.

Die Raum-Komplexität bezieht sich auf die Abschätzung des Speicherbedarfs der Daten bzw. der Informationen, die für einen Algorithmus benötigt wird.

Die psychologische Komplexität spiegelt das Programmverständnis des Programmierers und die Handhabbarkeit eines Algorithmuses wieder. Gerade die psychologische Komplexität wird häufig deutlich unterschätzt. Sie wird gering gehalten, wenn der Programmierer sich an die Vorgaben der Programmierstile hält. Dazu gehören u.a.

• Strukturierung des Quelltextes durch Einrückung und Leerzeilen

• Kommentierung des Quelltextes

• Unterteilung des Programmes in logische Einheiten (Module) und Funktionen

Einige dieser Aspekte wurden im Kapitel 5: Programmierstile bereits angesprochen.

Die Komplexität wird durch die O-Notation ausgedrückt. Diese wurde von dem deutschen Mathematiker Paul Bachmann (* 1837 † 1920) im Jahr 1894 im Rahmen seines Buches über die analytische Zahlentheorie eingeführt und später von dem ebenfalls deutschen Mathematiker Edmund Landau (* 1877 † 1938) weiter entwickelt. Dabei gibt die O-Notation den schlechtesten Fall (worst case) bei einem Algorithmus an; z.B. wenn bei einem unsortierten Array nach einem Eintrag gesucht wird und der letzte Eintrag im Array ist das gesuchte Element. Durch die Angabe des schlechtesten Falles wird eine obere Grenze angegeben, die von dem Algorithmus nicht überschritten werden kann.

Daneben gibt es noch den besten Fall (best case), der aber wegen seiner Seltenheit und seiner geringen Aussagekraft nicht weiter betrachtet wird, und den durchschnittlichen Fall (average case), für den die Ω-Notation eingeführt wurde.

Im allgemeinen wird zwischen den folgenden O-Notationen unterschieden (kein Anspruch auf Vollständigkeit!). Dazu wird jeweils ein Anwendungsbeispiel angegeben, das im allgemeinen die angegebene Komplexität hat.

Die folgende Tabelle zeigt recht eindrücklich, wie sich die einzelnen Komplexitäten schon für kleine Datenmengen n entwickeln.

Um die Komplexitäten von mehrschrittigen Funktionen schneller und einfacher abschätzen zu können, wurden zur O-Notation auch Rechenregeln entwickelt. Einige davon werden im folgenden vorgestellt. Dabei wird eine unbekannte oder allgemeine Komplexität mit O(f(n)) bezeichnet.

• O(1) = c, d.h. der konstante Aufwand wird mit der Konstanten c bezeichnet.

• c * O(f(n)) = O(c * f(n)) = O(f(n)), da bei der Betrachtung der Verdopplung der Datenmenge n die Konstante nicht ins Gewicht fällt und daher vernachlässigt werden kann.

• O(f(n)) + O(f(n)) = 2 * O(f(n)) = O(f(n)) (siehe vorige Regel)

• Bei f(n) = c_k * n^k + c_k-1 * n^k-1 + … + c₀ gilt O(f(n)) = O(n^k), d.h. es wird für die Komplexität immer nur die höchste Potenz berücksichtigt, die niedrigeren Potenzen werden vernachlässigt.

• O(f(n)) + O(g(n)) = O( max{f(n), g(n)} ), auch hier wird nur die höhere Komplexität berücksichtigt.

• O(f(n)) * O(g(n)) = O(f(n) * g(n))

Um die Laufzeit-Komplexität abschätzen zu können, müssen die Komplexitäten der grundlegenden Elemente bekannt sein.

Einfache Anweisungen

Einfache Anweisungen (Zuweisungen, Berechnungen, Vergleiche, Deklarationen und Definitionen, Ein- und Ausgabe, usw.) sind nicht von der Menge der Daten abhängig. Sie haben daher einen konstanten Aufwand bzw. die Komplexität O(1).

Sequenz

Eine Sequenz ist eine Aneinanderreihung von einfachen Anweisungen oder von mehreren Algorithmen, die von der Datenmenge n abhängen. Die Summe der Komplexitäten ist nach den Rechenregeln vom vorigen Abschnitt O(f(n)) + O(g(n)) + O(h(n)) = O( max{f(n), g(n), h(n)} ). D.h. es wird in einer Sequenz nur der Algorithmus mit der größten Komplexität betrachtet.

Schleife

Die Komplexität einer Schleife, die n-mal durchlaufen wird, ist im allgemeinen gleich O(n). Nun kann der Schleifenkörper selbst von der Datenmenge n abhängig sein, z.B. durch eine weitere innere Schleife, die ebenfalls n-mal durchlaufen wird. Dann gilt O(n) * O(n) = O(n²). Verallgemeinert kann also gesagt werden, dass durch eine Schleife die Komplexität des Schleifenkörpers mit n multipliziert wird: O(n) * O(f(n)) = O(n * f(n)).

Verzweigung

Bei einer Verzweigung wird nur ein Zweig der Verzweigung abgearbeitet. Da mit der O-Notation immer der schlimmste Fall betrachtet wird, ist die Gesamt-Komplexität der Verzweigung gleich der Komplexität von dem Zweig, der die höhere Komplexität hat, d.h. gleich O( max{f(n), g(n)} ).

Obwohl die O-Notation ein mathematisches Werkzeug ist, bedarf es des Mitdenkens und der Interpretation. Folgendes sollte bei der Anwendung der Komplexitäten immer berücksichtigt werden:

1. Die O-Notation gibt den Aufwand im schlimmsten Fall (worst case) an. Damit ist sie eine obere Grenze, was nicht heißen muss, dass der Algorithmus jemals die abgeschätzte Komplexität erreichen wird. Vielmehr ist es die Angabe, dass der Algorithmus niemals mehr Zeit oder mehr Speicher benötigen wird. Daher macht es durchaus Sinn, sich auch den durchschnittlichen und auch den besten Fall anzusehen.

2. Die oben verwendete Konstante, die die Komplexität O(1) (konstanter Aufwand) hat, wurde bisher immer vernachlässigt, da sie unabhängig von der Datenmenge ist. In dieser Konstanten ist die tatsächliche Laufzeit (oder der tatsächlich benötigten Speicherbedarf) enthalten. Es sollte natürlich klar sein, dass ein Algorithmus mit der Komplexität O(n³), bei dem für jeden Durchlauf nur einen Bruchteil einer Sekunde benötigt wird, einem Algorithmus mit der Komplexität O(n), der für jeden Durchlauf ein Jahr benötigt, vorzuziehen ist.
   Beispiel:
   Ein Algorithmus mit der Komplexität O(n³) benötigt pro Durchlauf 1 Mikrosekunde. Bei einer Datenmenge von n = 100.000 ergibt sich dann eine Laufzeit von knapp 32 Jahren. Dagegen benötigt ein Algorithmus mit der Komplexität O(n) und einer Laufzeit von 1 Jahr pro Durchlauf bei der gleichen Datenmenge insgesamt 1.000.000 Jahre!
   Daher sollte auch immer ein Blick auf den konstanten Aufwand geworfen werden.

3. Auch bei der Vernachlässigung der Komplexitäten mit geringeren Potenzen (siehe Rechenregeln; es wird bei einer Sequenz immer nur die höchste Komplexität berücksichtigt) kann es zu falschen Ergebnissen kommen, wenn deren Faktoren deutlich größer sind als der Faktor der höchsten Komplexität – gerade bei kleinen Datenmengen wirkt sich dies sehr stark aus.

4. Denn die O-Notation ist eine Aufwandsabschätzung für sehr große Datenmenge – eigentlich sogar der Grenzwert für Datenmengen gegen Unendlich. Daher sollte auch immer die tatsächliche Datenmenge bei den Betrachtungen berücksichtigt werden.

Voriges Kapitel: 7. Automaten

Nächstes Kapitel: 9. Sortier-Algorithmen