Algorithmische Komplexität

Komplexität: Ressourcenbedarf eines Algorithmus (Zeitkomplexität, Platzkomplexität; vielleicht auch Kostenkomplexität etc.)

• Forschungsgegenstand der Komplexitätstheorie
• hier hauptsächlich Zeitkomplexität

einfaches Beispielproblem: "Gegeben ist eine sortierte Liste von Wörtern (Schlagwörter im Wörterbuch). Finde ein bestimmtes Wort."

• naive Idee: jedes Wort nacheinander anschauen -> lineare Laufzeit (Verdopplung der Wörtermenge verdoppelt die zu erwartende Suchzeit)
• kluge Idee: Bisektion -> logarithmische Laufzeit (Verdopplung der Wörtermenge erfordert nur einen zusätzlichen Schritt)

Beschreibung von Komplexität: Landau-Symbole

• wichtigste Form: f = O(g) heißt, dass f "nicht wesentlich schneller als g wächst (sprich: f(n)/g(n) bleibt beschränkt, wenn n -> ∞)
• Beispiel: naive Suche über eine Liste von n Elementen hat eine Laufzeit in O(n), Bisektion hat eine Laufzeit in O(log n)

etwas komplexeres Beispiel: Sortieralgorithmen ("Gegeben ist eine Liste von Zahlen/Wörtern/etc. Sortiere diese Liste.")

• Live-Beispiel: Skatkarten mischen und dann sortieren -> Auf welche Art und Weise sortieren wir intuitiv?
• Sortieralgorithmen auf Computern: zwei Grundbausteine
  • Vergleich von zwei Elementen
  • Tauschen von zwei Elementen
• anhand von Skatkarten diskutierbar:
  • Insertionsort: O(n^2)
  • Quicksort: O(n log n)
  • Mergesort: O(n log n)
• wünschenswerte Eigenschaften:
  • Lokalität (Timsort!, siehe STP007)
  • Stabilität (Mergesort!)
  • Codegröße (Quicksort!)

Schauempfehlung (mit Epilepsie-Warnung): Visualisierung verschiedener Sortieralgorithmen

im Gespräch erwähnt:

• Bacon-Zahl
• Erdős-Zahl
• How large is 52 factorial?