Vorlesung 15. Januar 2009. Stefan Schmid @ TU München, 20092 Algorithmen und Datenstrukturen Analyse von Algorithmen: mit Referenzmaschine Registermaschine

Vorlesung 15. Januar 2009

Stefan Schmid @ TU München, 2009 2

• Algorithmen und Datenstrukturen

• Analyse von Algorithmen: mit Referenzmaschine „Registermaschine“

• Wichtige Kriterien: Zeit (Anzahl Schritte) und Platz (Speicher)

• Kostenmodelle:- uniform (Anzahl Elementarschritte, Anzahl Zellen)

- logarithmisch (bezgl. Maximale Operanden / Werte)

- kann grossen Unterschied machen!

Was bisher geschah...

• Analysen: worst-case vs average-case vs best-case


Sortierproblem

• Eingabe: Sequenz s = <e1,…,en> mit Ordnung <= auf den Schlüsseln key(ei)(Beispiel: )

• Ausgabe: Sequenz s´ = <e´1,…,eń>, so dass key(ei)<=key(ei+1) für alle 1<=i<n und s´ eine Permutation von s ist(Beispiel: )1 3 10 14 195

5 10 1 14 319

• Bisher: Selection Sort und Insertion Sort

- beide quadratische Laufzeit

- O(n2) und (n2), also (n2)


Selection Sort: Beispiel

5 10 1 3 1419

i j

j Element grösser => weiter

Prinzip: Suche Minimum im Feld rechts von i und füge es bei i ein.(Ausgabesequenz = vorne am Array)

Laufe ganzes Feld nach rechts durch, swappe mit i-Position wann immer ein neuer Rekord!

Achtung: Prinzip gleich wie VL, aber leicht anders (von links nach rechts)!



5 10 1 3 1419

i j




5 10 1 3 1419

i j

j Element kleiner => swap!



1 10 5 3 1419

i j




1 10 5 3 1419

i j

j Element grösser => weiter!



1 10 5 3 1419

i j

j Element grösser => i++; j=i+1!



1 10 5 3 1419

i j




1 10 5 3 1419

i j




1 5 10 3 1419

i j




1 5 10 3 1419

i j




1 3 10 5 1419

i j




1 3 10 5 1419

i j




1 3 10 5 1419

i j




1 3 19 5 1410

i j




1 3 19 5 1410

i j




1 3 19 10 145

i j




1 3 19 10 145

i j




1 3 19 10 145

i j




1 3 10 19 145

i j

j Element grösser => i++; j:=i+1!



1 3 10 19 145

i j




1 3 10 14 195

i j

Fertig!


Insertion Sort: Beispiel

5 10 1 3 1419

ij

j Element kleiner als j+1 Element => weiter

Prinzip: Für immer grössere i, lasse i-tes Element „runterblubbern“,soweit bis Nachfolger kleiner => alles links von i ist sortiert!(Ausgabesequenz = vorne am Array)

Laufe Feld nach links durch soweit wie nötig, swappe mit Nachbarposition wann immer ein neuer Rekord!

Achtung: Prinzip gleich wie VL, aber leicht anders!



5 10 1 3 1419

ij




5 10 1 3 1419

ij




5 10 1 3 1419

ij

j Element grösser => swap



5 10 19 3 141

ij

j Element grösser => swap



5 1 19 3 1410

ij

j Element grösser als (j+1) Element => swap



5 1 19 3 1410

ij




1 5 19 3 1410

ij


Die 1 ist ganz „runtergeblubbert“!



1 5 19 3 1410

ij




1 5 3 19 1410

ij




1 5 10 19 143

ij




1 3 10 19 145

ij

j Element kleiner als (j+1) Element => weiter

Die 3 „blubberte“ nur an zweitunterste Stelle.



1 3 10 19 145

ij


Die 14 „blubbert“ nur eine Stelle weit.



1 3 10 14 195

ij



1 3 10 14 195

ij

Rest ok, alles schon sortiert gegen links => fertig!


Mergesort

Idee: zerlege Sortierproblem rekursiv in Teilprobleme, die separat sortiert werden und dann verschmolzen werden

10 5 1 14 319

5 10 1 3 1419

1 3 10 14 195

rekursiv

merge


Beispiel (Wikipedia)

Beim rekursivenAbstieg passiert nichts!

Erst beim Aufstieg wirdsortiert (via merge)!


Zwei sortierte Felder mergen

5 10 1 3 1419

merge

j k

m



5 10 1 3 1419

1

merge



5 10 1 3 1419

1

merge



5 10 1 3 1419

1 3

merge



5 10 1 3 1419

1 3

merge



5 10 1 3 1419

1 3 5

merge



5 10 1 3 1419

1 3 5

merge



5 10 1 3 1419

1 3 105

merge



5 10 1 3 1419

1 3 105

merge



5 10 1 3 1419

1 3 10 145

merge



5 10 1 3 1419

1 3 10 145

merge



5 10 1 3 1419

1 3 10 14 195

merge



5 10 1 3 1419

1 3 10 14 195

merge


Mergesort

Theorem 5.2: Mergesort benötigt O(n log n) Zeit, um eine Folge der Länge n zu sortieren.

Beweis:• T(n): Laufzeit bei Folgenlänge n• T(1) = (1) und

T(n) = T(bn/2c) + T(dn/2e) + (n)• aus Übungsaufgabe: T(n)=O(n log n)


Quicksort

Idee: ähnlich wie Mergesort, aber Aufspaltung in Teilfolgen nicht in Mitte sondern nach speziellem Pivotelement

10 5 1 14 319

5 1 3 1419

1 3 14 195

10

rekursiv

10

ordne nach<10 und >10

unsortiert!


Quicksort

Procedure Quicksort(l,r: Integer)// a[l..r]: zu sortierendes Feldif r>l then v:=a[r]; i:=l-1; j:=r repeat // ordne Elemente nach Pivot v repeat i:=i+1 until a[i]>=v repeat j:=j-1 until a[j]<=v if i<j then a[i] $ a[j] until j<=i a[i] $ a[r] Quicksort(l,i-1) // sortiere linke Teilfolge Quicksort(i+1,r) // sortiere rechte Teilfolge


Quicksort: Quicksort

i: gehe solange nach links bis grösser als Pivotj: gehe solange nach rechts bis kleiner als Pivot

=> dann mache swap!

Jetzt rekursiv beide Hälften mit QS!


Quicksort: Beispiel

5 10 1 3 1419

Pivot!

i j

i++, dann i: gehe solange nach rechts bis >= Pivotj--, dann j: gehe solange nach links bis <= Pivot


Quicksort: Beispiel

5 10 1 3 1419

Pivot!

i j

i<j => ok => swap!


Quicksort: Beispiel

5 10 1 19 143

Pivot!

i j

i++ solange bis >= Pivotj-- solange bis <= Pivot


Quicksort: Beispiel

5 10 1 19 143

Pivot!

ij

i<j : falsch => kein swap mehr!

Nun noch Pivos an Position i swappen!


Quicksort: Beispiel

5 10 1 14 193

Pivot ist an richtigersortierter Position! Wird nicht mehr ändern!

Sortiere rekursiv! Sortiere rekursiv!


Quicksort

Problem: im worst case kann Quicksort (n2) Laufzeit haben (wenn schon sortiert)

Lösungen: • wähle zufälliges Pivotelement

(Laufzeit O(n log n) mit hoher W.keit)• berechne Median (Element in Mitte)

! dafür Selektionsalgorithmus (Kap 5.5)


Quicksort: Worst-Case

1 3 10 14 195

Pivot 1

Sortiere rekursiv!



1 3 10 14 195

Pivot 2

Sortiere rekursiv!



1 3 10 14 195

Pivot 3

Sortiere rekursiv!



1 3 10 14 195

Pivot 3

Insgesamt n Rekursionen, jede Rekursion erfordertI (für i=1..n) Vergleiche mit Pivotelement => O(n2)


Veranschaulichung (1)

Falls Pivot immer in der Mitte:

...

O(log (n)) viele Stufen

Wieviele Vergleichesind nötig pro Stufe?



Falls Pivot immer in der Mitte:

...

n-1 Vergleiche mit Pivot

~ 2 * n/2 Vergleiche mit Pivots

~ 4 * n/4 Vergleiche mit Pivots

Tiefe i: 2î Subarrays der Grösse n/2î. Bereits fixierte Pivots: 1+2+4+...+2î.



Falls Pivot immer am Rand landet:

...




Auch auf jeder Stufe ca. n Vergleiche!Was ist der Unterschied??



Falls Pivot immer am Rand landet:

...

O(n) Stufen -- nur ein neues fixesElement pro Stufe!

Tiefe i: 1 Subarray der Grösse n-i. Bereits fixierte Pivots: i.


3

5 8

10 9 12 15

11 18

5 8

10 9 12 15

11

18

Invariante: H[k] ist minimal für Teilbaum von H[k]

: Knoten, die Invariante eventuell verletzen

Heap: DeleteMin

Achtung: Min Heap!


5 8

10 9 12 15

11

5

8

10 9 12 15

11

18

18



Heap: DeleteMin


5

8

10 9 12 15

11

5

8

10

9

12 15

11

18

18



Heap: DeleteMin


Untere Schranke

Permutation der Eingabefolge:• Menge S:

• Eingabefolge:

10 5 1 14 319

1 3 10 14 195


Untere Schranke

Wenn der Algorithmus sortieren kann, kann er auch die Permutation ausgeben (u.u.).

10 5 1 14 319

1 3 10 14 195


Untere Schranke

Beliebiger vergleichsbasierter Algo als Entscheidungsbaum:

Zeit

e1<e2?

e3<e4? e5<e6?

Menge aller Permutationen

1 2

ja nein

i : Permutationsmenge, die Bedingungen bis dahin erfüllt

= 1 [ 2


Untere Schranke


Zeit

e1<e2?

e3<e4? e5<e6?

1

2 3

ja nein

i : Permutationsmenge, die Bedingungen bis dahin erfüllt

1 = 2 [ 3


Untere Schranke


Zeit

e1<e2?

1 2

1 2

ja nein

i : eindeutige Permutation der Eingabefolge

= {1, 2}


Untere Schranke


Zeit

e1<e2?

1 2

1 2

ja nein

Wieviele Blätter muss Entscheidungsbaum haben?

= {1, 2}


Untere Schranke


Zeit

e1<e2?

1 2

1 2

ja nein

Mindestens n! viele Blätter!

= {1, 2}


Untere Schranke


Zeit

Baum der Tiefe T:Höchstens 2T Blätter

2T >= n! ,T >= log(n!) = (n log n)

Jeder vergleichsbasierte Algo hat (n log n) Laufzeit

e.g., O() folgt aus n! ¸ (n/e)n


Beispiel

Ein Algo für Arrays der Grösse 3:

{(123),(132),(213),(231),(312),(321)}

Position 2 < Position 1Position 1 < Position 2

{(123),(132),(231)} {(213), (312),(321)}p2 < p3?

{(123)} { (132),(231)} ...

p1 < p3?{ (132)} {(231)}

Um (132) zu sortieren brauchtdieser Algo 3 Vergleiche![log(3!) = 2.58...]




Radixsort

Ideen: • Benutze Repräsentation der Schlüssel• K-adische Darstellung der Schlüssel• Sortiere Ziffer für Ziffer gemäß KSort• Behalte Ordnung der Teillisten bei


Radixsort

Procedure Radixsort(s: Sequence of Element)for i:=0 to d-1 do KSort(s,i) // sortiere gemäß keyi(x) // mit keyi(x) = (key(x) div Ki) mod K,

// d.h. kleinste Ziffer zuerst!

Laufzeit: O(d(n+K))Falls maximale Zahlengröße O(log n), dann alle Zahlen <= nd für konstantes d.In diesem Fall Laufzeit für n Zahlen sortieren O(n).


Radixsort

Beispiel (Ziffern des Zehnersystems, K=10):

Ordnung nach Einerstelle:

12 203 3 74 24 17 112

0 1 2 3 4 5 6 7 8 9


Radixsort

Ergebnis nach Einerstelle:

Ordnung nach Zehnerstelle:

12 112 203 3 74 24 17

0 1 2 3 4 5 6 7 8 9


Radixsort

Ergebnis nach Zehnerstelle:

Ordnung nach Hunderterstelle:

203 3 12 112 17 24 74

0 1 2 3 4 5 6 7 8 9

Reihenfolge von Zahlen mitgleicher Zehnerstelle behalten wir bei!(Stabilität von k-Sort!)


Radixsort

Ergebnis nach Hunderterstelle:

Sortiert!

3 12 17 24 74 112 203

Zauberei???


Radixsort

Korrektheit:• Für jedes Paar x,y mit key(x)<key(y) gilt:

es existiert i mit keyi(x)<keyi(y) und keyj(x)=keyj(y) für alle j>i (j wächst gegen links: kleine Stellen zuerst)

• Schleifendurchlauf für i: poss(x)<poss(y)(poss(z): Position von z in Folge s)

• Schleifendurchlauf für j>i: Ordnung wird beibehalten wegen pushBack in KSort

3135 < 3146


Radixsort: Beispiel Wikipedia

Phase 1

Phase 2

Phase 3

Input

Output

Documents

Vorlesung 15. Januar 2009. Stefan Schmid @ TU München, 20092 Algorithmen und Datenstrukturen Analyse von Algorithmen: mit Referenzmaschine Registermaschine