Die Zeitkomplexität des Sortierproblems

Eine untere Schranke für Sortieralgorithmen

Bevor die Komplexität des Sortierproblems abgeschätzt werden kann, muss geklärt werden, welche Operationen zur Lösung des Problems zugelassen sind. Es muss also das zu Grunde liegende Berechnungsmodell präzisiert werden.

Wir gehen im Folgenden davon aus, dass die gesuchte Anordnung der zu sortierenden Liste nur über Vergleiche von Listenelementen (und deren Vertauschungen) gewonnen wird und nicht über sonstige Vergleiche (wie z.B. ob sie größer als eine bestimmte Zahl sind). Wir betrachten also nur vergleichsbasierte Sortieralgorithmen.

Die Betrachtungen im letzten Abschnitt verdeutlichen, dass es zu jedem vergleichsbasierten Sortieralgorithmus (für jede Listenlänge) einen zugehörigen Entscheidungsbaum gibt. Die Tiefe des Entscheidungsbaum (in Abhängigkeit der Listenlänge) legt das worst-case-Verhalten des Algorithmus fest.

Um eine untere Schranke für das worst-case-Verhalten von Sortieralgorithmen zu gewinnen, schauen wir uns die Tiefe von optimalen Entscheidungsbäumen (in Abhängigkeit der Listenlänge) an.

Um k verschiedene Anordnungen nur mit Entscheidungen zu erzeugen, benötigt man einen Entscheidungsbaum mit einer Tiefe der Größenordnung log₂(k). Wenn k = 2^m eine Zweierpotenz ist, dann reicht die Tiefe m. Ansonsten benötigt man als Tiefe den Exponenten von der von k aus nächst größeren Zweierpotenz.

Wenn beispielsweise k = 24, dann benötigt man eine Tiefe log₂(32), also die Tiefe 5.

Um eine Aussage über Listen beliebiger Länge treffen zu können, muss man wissen, wie viele Anordnungen jeweils möglich sind: Bei n Listenelementen gibt es n! = 1*2*...*n verschiedene mögliche Anordnungen der Listenelemente.

Fasst man beide Ergebnisse zusammen, so erhält man folgende Aussage: Um eine Liste mit n Elementen zu sortieren, benötigt man einen Entscheidungsbaum, der eine Tiefe der Größenordnung log₂(n!) hat.

Jeder vergleichsbasierte Sortieralgorithmus hat demnach ein worst-case-Verhalten, das durch die Funktion K(n) = log₂(n!) abgeschätzt werden kann.

Mathematiker haben gezeigt, dass n! ≥ (n/2)^(n/2) gilt. Mit dieser Abschätzung erhält man log₂(n!) ≥ (n/2)*log₂(n/2). Hieraus ergibt sich, dass jeder vergleichsbasierte Sortieralgorithmus ein worst-case-Verhalten hat, das nach unten durch die Funktion K(n) = (n/2)*log₂(n/2) abgeschätzt werden kann. Betrachtet man - wie üblich - nur das asymptotische Verhalten, so zeigt dies, dass das worst-case-Verhalten eines beliebigen Sortieralgorithmus von der Ordnung n*log₂(n) sein muss.

Damit ist eine Schranke zur Beschreibung der Komplexität des Sortierproblems gefunden. Die Komplexität des Sortierproblems ist von der Ordnung n*log₂(n) - sofern man ein vergleichsbasiertes Berechnungsmodell zu Grunde legt.