Algorithmen

Zeitkomplexität von Algorithmen

Ziel ist immer die effiziente Ausführung von Algorithmen in einer minimalen Zeit, mit einem minimalen Aufwand (Ausführungsaufwand).

Der Ausführungsaufwand ist zu unterscheiden vom Aufwand den Algorithmus zu entwickeln, dem Entwicklungsaufwand. Langsame Anwendungen sind leider oft das Resultat von Implementierungen bei denen die Kostengründe für den Entwicklungsaufwand zu einem höheren Ausführungsaufwand führen...

Ausführungsaufwand versus Entwicklunggaufwand

Der Ausführungsaufwand hängt von vielen Faktoren ab. Viele Faktoren beruhen auf den unbekannten Komponenten des Ausführungssystems:

  • Betriebssystem
  • Prozessor, Prozessorgeschwindigkeit
  • Hauptspeichergröße und - geschwindigkeit
  • etc.

Die verlässlichste Art und Weise zur Beurteilung der Zeiteffizienz von Algorithmen ist die Abschätzung der Anzahl der Verarbeitungsschritte in Abhängigkeit von der Anzahl der Daten die zu verarbeiten sind.

Definition
Ordnung "O" eines Algorithmus
Die funktionale Abhängigkeit (bzw. Proportionalität) zwischen der Zahl der Ausführungsprogrammschritte und der Zahl (n) der zu verarbeitenden Datenelemente

Beispiele

  • O(n): Ein Algorithmus hat eine lineare, proportionale Abhängigkeit von der Anzahl der Elemente. Verdoppelt sich die Anzahl der Elemente, so verdoppelt sich auch die Anzahl der Ausführungsschritte und damit die Ausführungsdauer
  • O(n2): Die Anzahl der Ausführungsschritte steigt mit dem Quadrat der zu behandelten Element. Der Ausführungsaufwand vervierfacht sich bei der Verdopplung der Ausführungsschritte.
  • O(log n): Die Anzahl der Ausführungsschritte steigt mit dem Logarithmus der Anzahl der Elemente

Hierdurch ergeben sich verschiedene Kategorien von Problemen:

Praktisch ausführbare Algorithmen

Algorithmen die auch bei einer sehr viel größeren Zahl von Elementen in einer akzeptablen Zeit ausgeführt werden können.

Dies sind im Idealfall: O(n), O(log n), O (n*log n)

Man zählt hierzu aber auch Algorithmen mit einer polynomialen Ordnung wie O(n2) oder O(n3).

 Funktionen mit verschiedener Komplexität

Praktisch nicht mehr ausführbare Algorithmen

Praktisch nicht mehr ausführbare Algorithmen lassen sich nicht in akzeptabler Zeit bei größer werdenden Datenbeständen ausführen. Dies sind Algorithmen mit einer exponentiellen Ordnung. O(xn). Hierzu zählt auch das Problem des Handlungsreisenden mit einer Ordnung von O(n!).