Main /

Laufzeit Verhalten

Laufzeit Verhalten

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.

Groß-O-Notation

Algorithmenbeispiel

Kommentar

O(1)

  • Auslesen eines Wertes aus einer Hashtable,
    dabei spielt es keine Rolle, wie lange für die Berechnung des Hashwertes gebraucht wird, da die Berechnung konstant ist, also immer gleich viel Zeit in Anspruch nimmt.

O(log n)

while (n/2)

  • Durchsuchen eines auf- absteigend sortierten Arrays
  • Binary tree access

O(n)

for (n...)

  • Durchlaufen einer Schleife
  • Durchsuchen eines unsortierten Arrays

O(n log n)

  • Sortieren eines Arrays (mittels Quicksort)

O(n^2)

for (n...)

for (m...)
  • Bubblesort
  • Multiplikation einer Matrix mit einem Vektor

O(n^3)

for (n...)

for (m...)
for (o...)
  • Multiplikation zweier Matrizen

O(n^n)

for (n1...)

for (n2...)
for (n3...)

...

O(n!)

  • Traveling sales men problem

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

Frische Änderungen | Menü editieren
zuletzt geändert am 05.01.2016 09:12 Uhr von Lars
Edit Page | Page History