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$log₂(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$log₂(n!) Vergleiche.

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

Abschätzung des Wachstums: log₂(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).