Algorithmen I, SS 2015, gehalten am 11.05.2015, Vorlesung 09
1 hour 25 minutes Posted Dec 3, 2015 at 3:33 pm.
Sortieren & Co
Formaler
Anwendungsbeispiele
Beispiele aus Kurs/Buch
Überblick
Einfache Sortieralgorithmen
Sentinels am Beispiel Sortieren durch Einfügen
Einfache Sortieralgorithmen
Analyse
Sortieren durch Mischen
Beispiel
Mischen
Untere Schranken
Eine vergleichsbasierte untere Schranke
Baumbasierte Sortierer-Darstellung
Beweis
Randomisierung, Mittlere Ausführungszeit
Quicksort – erster Versuch
Quicksort – Analyse im schlechtesten Fall
Schlechtesten Fall: Beispiel
Quicksort – Analyse im besten Fall
Quicksort – zufälliger Pivot
Satz: Quicksort hat erwartete Laufzeit O(nlogn)
Beweissatz 1: Rekurrenzen
Exkurs: Harmonische Summe
0:00
1:25:29
Show notes
09: Vorlesung |
Watch Video
