Eine untere Schranke für die Medianbestimmung

Beweis: Gegenspielerargument (adversary argument)
n Elemente, o.B.d.A. n ungerade, alle Elemente paarweise verschieden. Die Menge aller Elemente wird in drei Teilmengen partitioniert: U enthält die Kandidaten für den Median, G enthält Elemente, die sicher größer als der Median sind und L enthält Elemente, die sicher kleiner als der Median sind. Anfangs sind alle Elemente in U. Der Algorithmus stellt nun Fragen der Form a_i < a_j. Der Gegenspieler gibt konsistente Antworten, die den Algorithmus jedoch dazu zwingen, möglichst viele Fragen zu stellen bevor die Antwort feststellen kann(d.h. U soll möglichst ungeordnet bleiben). Durch die (konsisten!) Antworten des Gegenspielers auf die ``$\stackrel{?}{<}$``-Queries des Algorithmus entsteht ein DAG. Gegenspieler hält DAG ``einfach``.
(Angenommen $y\gt z \text{ und } y\gt x \Rightarrow y$ soll sehr groß sein $\Rightarrow y\rightarrow G$)

Solange $\vert L\vert,\ \vert G\vert < \frac{n+1}{2}$, kann der Algorithmus annehmen, daß der Median in U ist. Solange U mindestens zwei unverglichene Elemente und keine Zusammenhangskomponente mit >2 Elementen enthält, kann der Algorithmus den Median nicht bestimmen.
Strategie des Gegenspielers: Zwei Phasen
Erste Phase: Query sei $x \stackrel{?}{<} y$:

i)

$x,y \in G \text{ bzw. } x,y \in L$: irgendeine konsistente Antwort

ii)

$x\in G \wedge \ y\in L\cup U (\text{bzw. } x\in L \wedge \ y\in G\cup U).$ Antwort: y<x (bzw. x<y).

iii)

$x,y\in U$

Die erste Phase endet, wenn $\vert L\vert = \frac{n-1}{2}$ oder $\vert G\vert = \frac{n-1}{2}$.Während der Phase 1 enthält U mindestens zwei (in U) maximale und mindestens zwei (in U) minimale Elemente (bzgl. des DAGs). $\Rightarrow$ Während Phase 1 kann der Algorithmus den Median mit Sicherheit nicht bestimmen.

Der Gegenspieler beginnt mit Phase 2:
|L| wird $\frac{n-1}{2}$ oder |G| wird $\frac{n-1}{2}$
o.B.d.A.:

$$\vert L\vert = \frac{n-1}{2}$$

Der Gegenspieler zwingt nun den Algorithmus, das minimale Element in U bzgl. der gesamten totalen Ordnung zu bestimmen (da dieses unter den Vorgaben der Median ist).

Analyse:
C:= Anzahl der Vergleiche
P:= Anzahl der Paare in U

i)

In der Phase 1 gilt folgende Invariante: $C-P+2\vert U\vert \geq 2n$
Beweis: vollständige Induktion:
Induktionsanfang: $0-0+2n\geq 2n$
Induktionsschritt: Gemäß der Tabelle. $\Diamond$

ii)

Sei C $\char93$ der Vergleiche am Ende der Phase 1, U die am Ende der Phase 2: In der Phase 2 werden noch $\geq \vert U\vert-1-\vert P\vert$ Vergleiche nötig. Die Anzahl der Vergleiche für alle Phasen:

Anzahl der Vergleiche $\geq C+\vert U\vert-1-\vert P\vert$.

Am Ende der Phase 1 gilt ja $C\geq 2n+\vert P\vert-2\vert U\vert$ (wg. Invariante).
$\Rightarrow$ Anzahl der Vergleiche:

$$\begin{split} \geq 2n+\vert P\vert-2\vert U\vert+\vert U\ve... ...ght\rceil \text{ da } \vert U\vert\leq \frac{n+1}{2}\end{split}$$

$\Diamond$