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...
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.
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). |
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!).
- Printer-friendly version
- Log in to post comments
- 7188 views