Die Rechenregeln für die Aufwände von Algorithmen erlauben dem Entwickler die Komplexitätsklasse eine Algorithmus abzuschätzen.

Hierzu muß der Entwickler zuerst bestimmen von welchem Parameter die Ausführungszeit primär abhängt.

Ein Beispiel: Konvertierung von Bildern Der Algorithmus soll eine Anzahl von n Bildern mit einer mittleren Größe vom m Byte konvertieren. Wird sich eher die Anzahl der Bilder n ändern? Wird sich eher die Größe der Bilder m ändern? Sehr wahrscheinlich wird die Anzahl der Bilder n nach dem bekanntmachen des Dienstes sehr schnell steigen. Die Größe m von Bildern, ist aber in der Vergangenheit durch neue Technologien, auch gestiegen. Es kann also sein, daß sich die Kriterien mit der Zeit ändern!

Hierzu geht der Entwickler in zwei Schritten vor:

1. Man bestimmt die Anzahl der auszuführenden Befehle eines Algorithmus in Abhängigkeit von den zu verarbeitenden Datenelementen n
2. Man vereinfacht den Term mit dem Gesamtaufwand derart, dass der Term und jeder Teilterm in der gleichen Komplexitätsklasse bleibt

Am Ende bleibt dann ein einfacher Ausdruck für die Komplexitätsklasse übrig.

Klassen von Komplexität

• konstant: O(1)
• logarithmisch: O(log(n))
• linear: O(n)
• jenseits von linear: O(n*log(n))
• polynomial: O(n²), O(n³), O(n⁴) etc.
• exponentiell: O(kⁿ)

Rechenregeln für einfache Betrachtungen

Gegeben sei eine Funktion f(n) mit dem Aufwand O(n). n sei die variable Anzahl der zu verarbeitenden Datenelemente

• Konstanten: Konstanten haben keinen Einfluss:
  • O(f(n)+k) = O(f(n))+k = O(f(n)) für k konstant
  • O(f(n)*k)=O(f(n))*k = O(f(n)) für k konstant
  • O(k) = O(1)
  • konstante Aufwände werden nicht einberechnet. Dies gilt für Multiplikation, sowie für die Addition.
• Nacheinander ausgeführte Funktion f und g
  • Der Aufwand O(f(n)) sei größer als der Aufwand von O(g(n))
  • O(f(n)+g(n))=O(f(n))+O(g(n)) = O(f(n))
  • ... der größere Aufwand gewinnt.
• Ineinander geschachtelte Funktionen oder Programmteile wie Schleifen f(g(n))
  • O(f(g(n))) = O(f(n))*O(g(n))
  • der Aufwand multipliziert sich.
  • Einschränkung: Hier wird davon ausgegangen, dass beide Schleifen von der gleichen Variablen abhängen!

Weitere Informationen

• bigocheatsheet.com: Know Thy Complexities!