Kurs:Algorithmen und Datenstrukturen/Vorlesung/Untere Schranke




Untere SchrankeBearbeiten

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

Eigenschaften der betrachteten AlgorithmenBearbeiten

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.

ProblembeschreibungBearbeiten

Zuerst die Problembeschreibung. Als Eingabe haben wir  . Als Vergleichstests nehmen wir  . Als vereinfachte Annahmen nehmen wir an, dass es nur verschiedene Elemente gibt, somit entfällt  . Die restlichen Test liefern alle gleichwertige Informationen. Sie bestimmen die Reihenfolge von  . Außerdem können sie und auf   beschränken. Somit haben wir eine binäre Entscheidung und es gilt entweder  

EntscheidungsbaumBearbeiten

Eine beispielhafte Eingabe ist   Die inneren Knoten vergleichen die Elemente  . Es wird ein Test durchgeführt ob   gilt oder nicht. Die Blätter sind Permutationen mit   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.

BeweisBearbeiten

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  . Der Binärbaum hat die Höhe h und maximal   Blätter, daraus folgt  . Wenn man nun logarithmiert, erhält man

 

 
 

LiteraturBearbeiten

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.