Laufzeitverhalten von Algorithmen

Zu jedem Algorithmus gibt es eine einfache Aussage, wie dieser sich in seiner Laufzeit verhält. Durch simples betrachten der Komplexität.

Groß-O-Notation

Mit der Angabe O(1) Groß O von eins soll zu einem Algorithmus angegeben werden, wie sein Laufzeitverhalten allgemein ist. Also eine einfache Aussage, wie komplex ein Algorithmus ist. Es ist völlig egal, wie lange dieser eine Schritt dauert, solange er konstant ist. Das heißt, O(100) ist eigentlich O(1).

Die Notation sagt nichts darüber aus, wie lange der Algorithmus an sich braucht. Wenn man allerdings weiß wie lange ein Algorithmus für n=1 braucht, dann kann man durch diese Notation Aussagen darüber machen, wie lange der Algorithmus für n=x braucht.

Die mit rot markierten Algorithmen haben ein sehr schlechtes Laufzeitverhalten. Das bedeutet auch, das selbst schnellste Computer diese Algorithmen nicht mehr in vernünftiger Zeit abarbeiten können.

Betrachtet wurde hier nur der average case.

Fazit

Wenn also ein Algorithmus ein schlechtes Laufzeitverhalten aufweißt, braucht nicht in die Compileroptimierung investiert werden, sondern in die Optimierung des Algorithmus an sich. Ein Algorithmus mit O(n log n) läuft einfach schneller als einer mit O(n^2) da helfen auch Quadprozessoren wenig.

Wobei für kleine n (<10) ein Algorithmus durchaus auch O(n!) schnell abgearbeitet werden kann. Was sind schon 9!=362880 Durchläufe auf GHz Maschinen. bei n>15 sieht die Sache dann schon wieder anders aus, n! von n=15 ist mehr als 1 Billion.

Links

• Wikipedia:Asymptotische_Laufzeit
• Sort contest