Algorithmen 090930Rückbilick Insertionsort Problem: sortieren einer Folge von n Zahlen. Zeitkomplexität von Insertionsort ist: T(n) = element O(n2) O(n2) ist die Menge von Funktionen, die höchstens quadratisch wachsen. Graph : Entwicklung der Laufzeit T(n) liegt immer unterhalb der Kurve (Parabel) f(n) = n2 eine Gerade g(n)=n schneidet in diesem Bespiel f(n) be 1 Der Wert ab dem die Menge beginnt heisse hier n(0) . für g(n) gilt also ab n(0)=1 gilf für alle n >= n(0) : g(n) <= c* n2 aber welche Funktionen liegen z.B. nicht in der Menge O unter der Voraussetzung das die Konstante c = 1 bleibt? Beispiel : 2hoch n
Quicksort 2 1 7 6 4 8 3 9 0 5 x setze x = den Wert des Mittleren elements der Folge a x=a[m] m ist der mittlere Folgenindex suche erste Element a[i] mit a[i] >= x suche das erste Element a[j] mit a[j] <= x tausche a[i] mit a[j] setze i= i + 1 setze j= j + 1 2 1 0 6 4 8 3 9 7 5 i j wiederhole solange i<=j gilt 6 vs 3 2 1 0 3 4 8 6 9 7 5 a[i] = 4 a[j] = 4 bedingungen gelten noch.... tausche 4 mit 4 erhöhe i und j 2 1 0 3 4 8 6 9 7 5 j i i ist nichtmehr <= j : abbruch alle Elemente links sind <= x alle Elemente rechts >= x
|
Zahlen & Daten
Publish |