Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Untere Schranke

Untere Schranke

Auf dieser Seite wird die untere Schranke für vergleichbare Sortierverfahren behandelt.

Eigenschaften der betrachteten Algorithmen

Die Komplexität im Durchschnittsfall und im Schlechtesten Fall ist nie besser als n ‧ log n. Die Sortierung erfolgt ausschließlich durch Vergleich der Eingabe-Elemente (comparison sorts), es handelt sich somit um vergleichsorientierte Sortierverfahren. Nun zeigen wir, dass n ‧ log n Vergleiche eine untere Schranke für „Comparison Sort“-Algorithmen ist. Dies heißt dann, dass Sortieralgorithmen mit Komplexität (schlechtester Fall) von n ‧ log n (z.B. MergeSort) asymptotisch optimal sind.

Problembeschreibung

Zuerst die Problembeschreibung. Als Eingabe haben wir $\langle a_{1},a_{2},...,a_{n}\rangle$. Als Vergleichstests nehmen wir $a_{i}<a_{j},a_{i}\leq a_{j},a_{i}\equiv a_{j},a_{i}\geq a_{j},a_{i}>a_{j}$. Als vereinfachte Annahmen nehmen wir an, dass es nur verschiedene Elemente gibt, somit entfällt $a_{i}\equiv a_{j}$. Die restlichen Test liefern alle gleichwertige Informationen. Sie bestimmen die Reihenfolge von $a_{i}~und~a_{j}$. Außerdem können sie und auf $a_{i}\leq a_{j}$ beschränken. Somit haben wir eine binäre Entscheidung und es gilt entweder $a_{i}\leq a_{j}~oder~a_{i}>a_{j}$

Entscheidungsbaum

Entscheidungsbaum

Eine beispielhafte Eingabe ist $a_{1}=6,a_{2}=8,a_{3}=5$ Die inneren Knoten vergleichen die Elemente $a_{i}~und~a_{j}$. Es wird ein Test durchgeführt ob $a_{i}\leq a_{j}$ gilt oder nicht. Die Blätter sind Permutationen mit $\langle \pi (a_{1}),...,\pi (a_{n})\rangle$ Sortieren heißt das Finden eines Pfades von der Wurzel zu einem Blatt. An jedem internen Knoten erfolgt ein Vergleich und entsprechend wird links oder rechts weiter gesucht. Ist ein Blatt erreicht, dann hat der Sortieralgorithmus eine Ordnung und die Permutation der Elemente ist erstellt. Daraus lässt sich schlussfolgern, dass jeder Sortieralgorithmus jede Permutation der n Eingabe-Elemente erreichen muss (n!). Daraus folgt wiederum, dass es n! Blätter geben muss, die alle von der Wurzel erreichbar sind. Andernfalls kann er zwei unterschiedliche Eingaben nicht unterscheiden und liefert für beide dasselbe Ergebnis und eins davon muss falsch klassifiziert sein. Die Anzahl an Vergleichen im schlechtesten Fall ist die Pfadlänge von Wurzel bis Blatt, oder auch Höhe genannt.

Somit erhalten wir das Theorem, dass jeder vergleichsorientierte Sortieralgorithmus im schlechtesten Fall mindestens n*log n Versuche braucht.

Beweis

Gegeben ist die Anzahl der Elemente n, h die Pfadlänge bzw. Höhe des Baums und b die Anzahl der Blätter. Jede Permutation muss in einem Blatt sein, das bedeutet $n!\leq b$. Der Binärbaum hat die Höhe h und maximal $2^{h}$ Blätter, daraus folgt $n!\leq b\leq 2^{h}$. Wenn man nun logarithmiert, erhält man

$h\geq log_{2}(n!)$

$\sim n\cdot log_{2}(n)$

$(genauer~=\Omega (n\cdot log_{2}(n)))$

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5.2.7 zu finden.