KIT | KIT-Bibliothek | Impressum | Datenschutz

10: Algorithmen I, Vorlesung, SS 2016, am 23.05.2016

Hofheinz. Dennis; KIT | Webcast [Hrsg.]

  • 0:00:00 Starten
  • 0:00:06 Erinnerung VL vom 18.05.2016
  • 0:03:16 Nachtrag zur unteren Schranke: Randomisierung, Mittlere Ausführungszeit
  • 0:05:11 Erinnerung: Mergesort
  • 0:06:50 Quicksort - erster Versuch
  • 0:13:10 Quicksort - Analyse im schlechtesten Fall
  • 0:17:36 Quicksort - Analyse im besten Fall
  • 0:21:12 Quicksort - zufälliger Pivot
  • 0:22:25 Satz: Quicksort hat erwartete Laufzeit 0( nlog n )
  • 0:26:39 Beweisansatz 1: Rekurrenzen
  • 0:52:14 Exkurs: Harmonische Summe
  • 0:58:34 Quicksort: Effiziente Implementierung
  • 1:07:20 Beispiel: Partitionierung, k=1
  • 1:12:06 Größerer Basisfall
  • 1:17:40 Halbrekursive Implementierung

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 30.05.2016
Erstellungsdatum 23.05.2016
Sprache Deutsch
DOI 10.5445/DIVA/2016-389
Identifikator KITopen-ID: 1000113981
Lizenz KITopen-Lizenz
Serie Algorithmen I, Vorlesung und Übung, SS 2016
Folge 10
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page