Eine bessere untere Schranke

Literatur: Samuel W. Bent, John W. John: ``Finding the median requires 2n comparisons.'' Proceedings of the $17^{\text{th}}$ Annual ACM Symposium on Theory of Computing 1985, p.213-216.



Bemerkung: $i=\left\lceil \frac{n}{2} \right\rceil \rightarrow \binom{n}{\left\lceil \frac{n}{2} \right\rceil} \approx \mathcal{O}(\frac{2^n}{\sqrt{n}}) \Rightarrow$ Höhe$(T)\geq 2n-o(n)$ (untere Schranke für Median).

Beweis: Gegenspielerargument + Abzählargument:
,,T hat viele Blätter``, A Teilmenge der Schlüssel, |A|=i;
T_A Teilbaum von T, alle Blätter von T_A sind auch Blätter von T.
Zu zeigen: T_A hat viele Blätter. ($\binom{n}{i}$ Möglichkeiten, T_A's zu konstruieren, Anzahl Blätter in T_A: 2^n-p, jedes Blatt von T kommt in höchstens n-i+1 T_A's vor)

Beobachtungen: Jedes Blatt w von T liefert folgende Informationen:

$$\text{answer}(w) \xrightarrow{\text{liefert}} i\text{-kleinstes Element }x$$

$$\text{little}(w) \xrightarrow{\text{liefert}} i-1\text{ Elemente } < x$$

$$\text{big}(w) \xrightarrow{\text{liefert}} n-i\text{ Elemente } \gt x$$

Wähle A als beliebige Teilmenge der n gegebenen Schlüssel, mit |A|=i. Wir geben für den Gegenspieler eine Strategie an, welche dazu führt, daß wir durch Zurechtschneiden aus T einen Baum T_A konstruieren können, so daß gilt:

• T_A ist Binärbaum
• jedes Blatt von T_A ist auch Blatt von T (keine zus. Blätter durch Abschneiden)
• für jedes Blatt w von T_A gilt: $\text{little}(w) \subseteq A$

Setze $\bar{A}$ das Komplement von A,

$$\begin{split} r:=&\ \sqrt{\log\left[\binom{n}{i}\frac{1}{n-i+1}\right]+3}\\ s:=&\ r-1\\ \end{split}$$

Es gilt: p=r+s-1

Die Konstruktion (das ``Zurechtstutzen``) von T erfolgt in zwei Phasen:

Erste Phase von der Wurzel nach unten (Breitensuche)
Betrachte Knoten x. Definiere:

• C(x) sind die Elemente $a \in A$ für die es kein $b \in A$ gibt und einen Knoten auf dem Pfad von der Wurzel von T zu x, an dem kein Vergleich mit einem anderen Element $b \in A$ erfolgt ist mit dem Ergebnis a<b.
• c(x) sind entsprechend die in x bekannten Minima in $\bar{A}$.
• s(x,a) $(a \in A)$ ist die Anzahl der Elemente $\in \bar{A}$ (genauer: $\in \text{c}(x)$) mit denen a auf dem Pfad von Wurzel von x verglichen wurde.

Regeln für Phase 1:
Es werden in Knoten x die Elemente a und b verglichen:

Regel 1.1: Falls $a \in A$ und $b \in A$ behalte x in T_A bei.

Regel 1.2: Falls $a \in \bar{A}$ und $b \in \bar{A}$ behalte x in T_A bei.

Regel 1.3: Sei o.B.d.A. $b \in \bar{A}$, $a \in A$. Ersetze den Unterbaum in T mit Wurzel x mit dem Unterbaum, dessen Wurzel das Kind von x ist, das dem Ergebnis entspricht (d.h. lasse den Vergleich a < b aus, nach Voraussetzung $A<\bar{A}$).

Phase 1 läuft solange $\vert\text{C}(x)\vert\leq r$. Ein Knoten auf einem Pfad in T von der Wurzel, bei dem $\vert\text{C}(x)\vert$ erstmals =r wird, heißt kritisch.Jeder Pfad in T von der Wurzel zu einem Blatt enthält genau einen kritischen Knoten.

Betrachte in T_A einen Pfad von der Wurzel zu einem kritischen Knoten x. Sei y ein Knoten auf diesem Pfad, z sein Kind.

Dann gilt:

$$\vert\text{C}(z)\vert+\vert\text{c}(z)\vert \geq \vert\text{C}(y)\vert+\vert\text{c}(y)\vert-1$$

Da $\vert\text{C}(\text{Wurzel})\vert=\vert A\vert=i$ und $\vert\text{c}(\text{Wurzel})\vert=\vert\bar{A}\vert=n-i$, müssen überhalb eines jeden kritischen Knoten x mindestens

$$i-\vert\text{C}(x)\vert+n-i-\vert\text{c}(x)\vert=n-r-\vert\text{c}(x)\vert$$

Vergleiche erfolgen. Von jedem kritischen Knoten abwärts arbeitet der Gegenspieler nach einer Strategie für Phase zwei. Sei x ein solcher kritischer Knoten. Dann ist $\vert\text{C}(x)\vert=r$.


Phase 2: Sei $a \in \text{C}(x)$ ein Element mit minimalem $\text{s}(x,a)$.

Fall 1: $\text{s}(x,a) \geq s$.

Betrachte irgendeinen Pfad von der Wurzel durch x zu einem Blatt w. Jeder solche Pfad muß mindestens n-1 Vergleiche enthalten, um answer(w) zu verifizieren: $\geq n-i$, für die answer(w) sich (direkt oder indirekt) als das kleinere Element ergibt, und $\geq i-1$, wo es sich als das größere ergibt.
Damit sind $\geq (r-1)s$ Vergleiche redundant (nämlich alle die, die zwischen Elementen aus C$(x)\setminus \{\text{answer}(w)\}$ und Elementen in $\bar{A}$ erfolgt sind).

Also:

$$\begin{split} \text{Tiefe}(T) &\geq n-1+s(r-1)\\ &= n-r-s-... ...g{\left[\binom{n}{i}\frac{2^{n-p}}{n-i+1}\right]} \end{split}$$

In diesem Fall folgt also die Behauptung direkt!

Fall 2: s(x,a)<s

Fall 2.1:

$\vert\text{c}(x)\vert\geq p$. Sei $S:=\text{c}(x)\cup\{a\}\setminus$Elemente, die in s(x,a) gezählt werden. Der Gegenspieler antwortet nun so, daß das Ergebnis das kleinste Element in S wird. Ist w ein Blatt in T_A unter x, so ist little(w)= $A-\{a\}$
Der Entscheidungsbaum T wird also gemäß folgender Regeln gestutzt (sei y der aktuelle Knoten und seien a und b die beiden Elemente, die in y verglichen werden):

Regel 2.1: falls $a,b\in S$, dann bleibt y erhalten.

Regel 2.2: andernfalls, sei oBdA. $a\in A\setminus S$ oder $b\in\Bar{A}\setminus S$; ersetze y mit seinem Unterbaum durch das Kind von y und dessen Unterbaum, das der Antwort von a<b entspricht.

Also, da überhalb des kritischen Knoten x keine zwei Elemente in S verglichen wurden, muß der Unterbaum von T_A unterhalb von x Tiefe $\geq \vert S\vert-1$ haben.
Zusammen mit Phase 1 ergibt sich eine Tiefe von T_A:

$$\begin{split} &\geq n-r-\vert\text{c}(x)\vert+\vert S\vert-... ...text{c}(x)\vert+1-(s-1)-1\\ &= n-r-s+1\\ &= n-p \end{split}$$

Fall 2.2: $\vert\text{c}(x)\vert < p$. $S:=\text{C}(x)$
Regeln so, daß der Algorithmus als Antwort das Maximum von S bestimmt. Tiefe von T_A:

$$\begin{split} &\geq n-r-\vert\text{c}(x)\vert+\vert S\vert-1\\ &\geq n-r-(p-1)+r-1\\ &= n-p \end{split}$$

In Wirklichkeit: Jeder Pfad in T_A von x zu Blatt hat mindestens die Länge n-p. Also enthält jedes T_A mindestens 2^n-p Blätter (von T). Alle T_A's zusammen enthalten $\geq\binom{n}{i}2^{n-p}$ Blätter von T, wobei jedes Blatt von T höchstens n-i+1 mal vorkommt: Sei w Blatt von T, dann ist $\text{little}(w)$ eindeutig bestimmt und muß, falls T_A w auch enthält, little($w)\subseteq A$ sein. Für das Element in A- little(w) gibt es $\leq n-i+1$ Möglichkeiten $\Rightarrow$ Anzahl Blätter von $T \geq \frac{1}{n-i+1} \binom{n}{i} 2n^{n-p} \Rightarrow$ Tiefe$(T)\geq \log \left[ \binom{n}{i} \frac{2^{n-p}}{n-i+1} \right]$.
$\Diamond$
Einige Referenzen:

1.

L. Hyafil: Bounds for selection. SIAM J.Compute 5(1976), p.109-114.

2.

S. Beut and John W. John: Finding median requires 2n compression. Proc 17. STOC (1985), p.213-216.

3.

John Welliaveetil John: A new lower bound for the set-partitioning problem. SIAM J. Compute 17 (1988), p. 640-647.

4.

Doris Dor and Uri Zwick: Median selection requires $(2+\varepsilon)n$ compression. Proc 37 FOCS (1996), p. 125-134

5.

Doris Dor and Uri Zwick: Selecting the median Proc 6 SODA (1995), p. 28-37