Komplexität von Problemen

Id: schrank.tex,v 1.1 2006-10-09 13:24:19 waldmann Exp

Wie schwer ist ein (algorithmisches) Problem?

Wieviel Ressourcen braucht jeder Algorithmus, der das Problem löst?

Satz: Für jedes Sortierververfahren für n Elemente gibt es eine Eingabe, für die das Verfahren $ \ge$log2(n!) Vergleiche ausführt.

Beweis: es gibt n! Permutationen, unter denen genau eine zu finden ist. Durch Elementvergleiche können wir in jedem Schritt die Anzahl der Möglichkeiten bestenfalls halbieren.

Damit brauchen wir $ \ge$log2(n!) Vergleiche.


Aufgabe: Werteverlauf dieser Funktion ausrechnen und mit bekannten Sortierverfahren/-Netzen vergleichen.

Abschätzung des Wachstums: log2(n!) $ \approx$ n log n

Folgerung: Sortieren hat eine Komplexität von wenigstens n log n. (D. h. mehr als linear, aber weniger als quadratisch.)

Folgerung: Sortieren durch binäres Einfügen ist optimal (durch lineares Einfügen nicht).



Johannes Waldmann 2009-01-12