2.3 Untere Schranke Ω(n log n)

Bevor man nach schnelleren Algorithmen sucht, fragt man: Wie schnell kann es überhaupt gehen? Eine untere Schranke gilt für jeden denkbaren Algorithmus, nicht nur für einen bestimmten.

Satz 1

Das Sortierproblem lässt sich in linearer Zeit auf das Konvexe-Hülle-Problem transformieren.

Daher benötigt die Berechnung der konvexen Hülle von $n$ Punkten in der Ebene $\Omega(n\log n)$.

Der Beweis steht auf den Folien nur als „siehe Tafel“, deshalb hier ausführlich.

Beweisidee: Reduktion

Bekannt ist: Vergleichsbasiertes Sortieren von $n$ Zahlen braucht im Worst Case $\Omega(n\log n)$ Vergleiche. (Ein Entscheidungsbaum muss $n!$ Permutationen unterscheiden und hat deshalb Höhe $\ge\log_2 n! = \Theta(n\log n)$.)

Strategie: Wir zeigen, dass man mit einem Hüllen-Algorithmus sortieren kann, wobei nur $O(n)$ Zusatzaufwand anfällt. Wäre die Hülle schneller als $n\log n$ berechenbar, dann auch das Sortieren. Das ist ein Widerspruch.

Beweis

Gegeben seien $n$ (verschiedene) reelle Zahlen $x_1,\dots,x_n$, die sortiert werden sollen.

Schritt 1 – Transformation, $O(n)$: Bilde jede Zahl auf einen Punkt der Normalparabel ab:

$x_i\ \mapsto\ p_i := (x_i,\ x_i^2).$

Schritt 2 – Alle Punkte sind Ecken der Hülle: Die Parabel $y=x^2$ ist eine streng konvexe Funktion. Für drei Parabelpunkte mit $x_a<x_b<x_c$ liegt der mittlere echt unterhalb der Sehne zwischen den äußeren. Kein Punkt liegt also auf oder in der Hülle der anderen, und jeder Punkt $p_i$ ist eine Ecke von $\mathcal{CH}(P)$.

Gib eigene Zahlen ein: Sie landen auf der Parabel, die Hülle läuft sie von links nach rechts ab, und heraus kommt die sortierte Folge.

Zahlen:

Eingabe: 3, -1.5, 4, 0.5, -3, 2, -0.5
Hülle gegen den Uhrzeigersinn ab dem linkesten Punkt (Nummern im Bild) ⇒ sortiert: -3 < -1.5 < -0.5 < 0.5 < 2 < 3 < 4 · Alle Punkte liegen auf der Parabel, also sind alle Ecken der Hülle.

Schritt 3 – Hülle berechnen: mit dem (hypothetischen) Hüllen-Algorithmus, Laufzeit $T_\text{CH}(n)$. Er liefert alle $n$ Punkte in Randreihenfolge.

Schritt 4 – Sortierte Folge ablesen, $O(n)$: Suche in der Ausgabe den Punkt mit dem kleinsten $x$ (lineare Suche). Von dort aus gegen den Uhrzeigersinn ablesen: Die Punkte kommen in aufsteigender $x$-Reihenfolge, denn die Hülle ist hier genau die Parabelkurve von links nach rechts (unten), geschlossen durch die Kante von ganz rechts zurück nach ganz links (oben). Die $x$-Koordinaten in dieser Reihenfolge sind die sortierte Folge.

Gesamt: Sortieren in $O(n) + T_\text{CH}(n) + O(n)$.

Schluss: Wegen der Sortierschranke gilt $O(n) + T_\text{CH}(n) = \Omega(n\log n)$, also $T_\text{CH}(n)=\Omega(n\log n)$. $\blacksquare$

Feinheiten (für die mündliche Prüfung)

• Die Schranke gilt im passenden Rechenmodell (algebraische Entscheidungsbäume). Dort ist auch das Quadrieren $x_i^2$ erlaubt. Im reinen Vergleichsmodell könnte man die Parabelpunkte gar nicht erzeugen.
• Entscheidend ist, dass die Ausgabe geordnet sein muss. Nur die Menge der Ecken zu bestimmen, ist ein anderes Problem (auch dafür gilt $\Omega(n\log n)$, aber mit aufwendigerem Beweis).

Folgerungen (Folie 12)

Die Komplexität des 2D-Hüllenproblems ist $\Theta(n\log n)$. Es gibt Algorithmen mit $O(n\log n)$, und schneller geht es nicht.

Ansatz	Laufzeit	optimal?
Naiv (2.2)	$O(n^3)$	nein
Divide-and-Conquer	$O(n\log n)$	ja
Scan-Line: Graham's Scan (2.4)	$O(n\log n)$	ja
Output-sensitiv: Jarvis' March (2.5), Hülle ist $h$-Eck	$O(h\cdot n)$	nein (Worst Case $n^2$)
Output-sensitiv: Chan (2.6)	$O(n\log h)$	ja, im output-sensitiven Sinne

Und output-sensitiv? Im Beweis oben ist $h=n$. Für output-sensitive Algorithmen gilt die feinere Schranke $\Omega(n\log h)$ [Kirkpatrick & Seidel 1986]. Für $h=n$ ist das wieder $\Omega(n\log n)$, für kleines $h$ ist es weniger.