Kleines Nachschlagewerk Informatik
Bestimmung der Komplexität
Worum geht es?
In der Schule ist die Ermittlung der Komplexitätsklasse ein Abschätzen. Das Master-Theorem etc. haben keine Bedeutung. Es gibt eine Reihe von Wegen, die zum Ziel führen können.
Analyse des Quelltextes
Oft kann man im Quelltext sehen, wie sich der Rechenaufwand etc. entwickelt. Zu den wichtigsten Kandidaten hierbei zählen Schleifen und rekursive Aufrufe.

Ist die Anzahl der Schelifendurchläufe von der Datenmenge n abhängig, so ist der Zusammenhang linear. Werden zwei Schleifen dieser Art geschachtelt, wächst die rechenzeit quadratisch, bei drei Schleifen kubisch.

Rekursive Aufrufe müssen genauer betrachet werden, sie können beispielsweise in exponentiellen als auch logarithmischen Zusammenhängen resultieren. Hierbei helfen Skizzen.
Skizzen
(Rekursive) Aufrufe von Routinen oder die Zerlegung von Daten lassen sich oft als Bild darstellen. Ein Beispiel ist die Suche in einem geordneten Array. Hier kann man imme rhalbieren und man erkennt, dass der Zusammenhang logarithmisch ist.
Vergleich mit Bekanntem
Kennt man zu einem Algorithmus die Komplexität, kann man prüfen, ob sich der zu untersuchende Algorithmus gleichartig verhält.
Funktionsssuche mit Datentabellen
Oft kann man eine Tabelle mit der Anzahl von Rechenschritten bei ein, zwei, drei etc. Datensätzen aufstellen. Dabei kann man zum einen schon einen Zusammenhang vermuten, man kann aber auch analog zum Vorgehen in Mathematik und Physik eine Funktion finden.
Summen
Algorithmen bestehen nicht nur aus wenigen Zeilen. Oft sind mehrere Schritte zu erledigen, die alle allein analysiert werden können. Bilden diese Schritte eine Sequenz, so müssen die rechenzeiten addiert werden. Da aber nur die Entwicklung interessiert, nimmt man - analog zum Verhalten von Funktionen im Unendlichen - den stärksten Term.


      O(n) + O(n^2) ergibt O(n^2)
      O(n) + 2 * O(n^3) + O(2^n) ergibt O(2^n)