\( \newcommand{\data}{\textnormal{data}} \newcommand{\lower}{\textnormal{lower}} \newcommand{\upper}{\textnormal{upper}} \newcommand{\array}{\textnormal{array}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\lognpone}{\ceil{\log_2(n+1)}} \newcommand{\bitsize}{\textnormal{bitSize}} \newcommand{\mult}{\textnormal{mult}} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\flows}{\textnormal{flows}} \newcommand{\pfrac}[2]{\left(\frac{#1}{#2}\right)} \)

Das Schema von QuickSelect war, dass wir ein zufälliges Pivot nehmen, das Array daran aufteilen, und in dem richtigen Teil rekursiv fortfahren. Der deterministische Algorithmus, den wir jetzt anschauen wollen, ist ganz ähnlich, nur dass das Pivot anders (nämlich geschickt deterministisch) gewählt wird.

def genericSelection (array, $k$): // sucht das Element von Rang $k$
  1. Wähle ein pivot aus array nach irgendeiner Strategie.
  2. smaller := [x for x in array if x < pivot]
  3. same := [x for x in array if x == pivot]
  4. greater := [x for x in array if x > pivot] # insgesamt $n$ Vergleiche, wenn wir's geschickt machen
  5. if $k \leq $ len(smaller):
    1. return genericSelection(smaller, $k$)
  6. else if $k \gt $ len(smaller) + len(same):
    1. return genericSelection(greater, $k$ - len(smaller) - len(same))
  7. else:
    1. return pivot

Der Median-of-Medians-Algorithmus

Wir nehmen der Einfachheit halber an, dass $n$ durch 10 teilbar ist. Der Median-of-Medians-Algorithmus verfährt auch nach dem Schema von genericSelection, nur dass das Pivot-Element selbst wieder rekursiv gewählt wird, aber recht geschickt.

def deterministicSelect(array, $k$): // sucht das Element von Rang $k$
  1. Teile die Liste in Blöcke von je fünf Elementen
  2. Sortiere jeden Block mit SelectionSort: $\frac{n}{5} \cdot {5\choose 2} = 2n$ Vergleiche
  3. Seien $c_1,\dots,c_{n/5}$ die Mediane dieser Blöcke.
  4. $\texttt{pivot} := \texttt{deterministicSelect}([c_1,\dots,c_{n/5}], n/10)$ # der Median der Mediane
  5. smaller := [x for x in array if x < pivot]
  6. same := [x for x in array if x == pivot]
  7. greater := [x for x in array if x > pivot] # insgesamt $n$ Vergleiche, wenn wir's geschickt machen
  8. if $k \leq $ len(smaller):
    1. return deterministicSelect(smaller, k)
  9. else if $k \gt $ len(smaller) + len(same):
    1. return deterministicSelect(greater, k - len(smaller) - len(same))
  10. else:
    1. return pivot

Um den Algorithmus deterministicSelect (üblicherweise als Median-of-Medians-Algorithmus bekannt) zu analysieren, skizzieren wir die Fünferblöcke und ordnen sie so an, dass das Pivot genau in der Mitte steht:

Die Mediane der Fünferblöcke sind die $w_i$, es gilt also $\{c_1, c_2, \dots, c_{n/5}\} = \{w_1,w_2,\dots,w_{n/5}\}$, nur dass wir die Blöcke in der Abbildung so angeordnet haben, dass $w_1, w_2, \dots, w_{l-1} \leq w_l \leq w_{l+1}, \dots, w_{n/5}$. Das Element $w_l$ ist unser Pivot.

Betrachten Sie nun beispielsweise $v_i$ für $i \leq l$. Wir wissen $v_i \leq w_i$ (weil jeder Block sortiert ist) und $w_i \leq w_l$, also $v_i \leq w_l$. Analog wissen wir für $j \geq l$, dass $w_l \leq w_j, x_j, z_j$ gilt. Die rot eingekreisten Elemente sind also alle $\leq$ Pivot; die blau eingekreisten $\geq$ Pivot.

Das Array left enthält also keine blauen Elemente; right enthält keine roten, und daher gilt

\begin{align*} |\texttt{left}| & \leq n - 3l = \frac{7n}{10} \\ |\texttt{right}| & \leq n - 3l = \frac{7n}{10} \\ \end{align*}

Egal wie die if-Kaskade in Zeilen 8, 9, 10 ausgeht, wird der nächste rekursive Aufruf mit höchstens $7n/10$ Elementen fortfahren. Sei $T(n)$ die maximale Anzahl an Vergleichen, die deterministicSelect auf einem Array der Länge $n$ tätigt. Es gilt $T(0) = T(1) = 0$. (In unserem Pseudocode oben haben wir den Basisfall vergessen!) Für $n \gt 1$ gilt

\begin{align*} T(n) & \leq 3n + \underbrace{T\pfrac{n}{5}}_{\textnormal{Zeile 4}} + \underbrace{T\pfrac{7n}{10}}_{\textnormal{Zeile 8.1 oder 9.1}} \ , \end{align*}

wobei wir uns hier das Auf- oder Abrunden sparen (wodurch unsere Rechnung streng genommen inkorrekt wird; ignorieren wir dies aber vorerst). Wie lösen wir diese Rekursion?

Rekursionsbaum. Nehmen wir allgemeine Werte $0 \lt \alpha, \beta \lt 1$ und $\alpha + \beta \lt 1$ (hier: $\alpha=1/5$ und $\beta = 7/10$) und untersuchen eine Rekursion der Form

\begin{align*} S(n) & = \begin{cases} cn + S(\alpha n) + S(\beta n) & \textnormal{ wenn $n \gt 1$,} \\ 0& \textnormal{ wenn $n \leq 1$.} \end{cases} \end{align*}

Zeichnen wir den "Rekursionsbaum" und schreiben in jeden Knoten den dortigen Wert von $n$:

Wobei der Baum aufhört, sobald wir einen Wert $\alpha^i \beta^j n \leq 1$ erreicht haben. Tun wir etwas ungehöriges: setzen wir den Baum bis zur Unendlichkeit fort. Wir haben also Knoten $\alpha^i \beta^j n$ für alle $i, j \in \N$.

Übungsaufgabe Zeigen Sie, dass es genau ${i+j \choose i}$ Knoten gibt, die mit $\alpha^i \beta^j n$ beschriftet sind.

Übungsaufgabe Zeigen Sie, dass die Zahlen in den Knoten auf Tiefe $k$ sich zu $(\alpha + \beta)^k n$ aufsummieren; die Wurzel hat dabei Tiefe $0$.

Insgesamt summieren sich die Zahlen also auf zu

\begin{align*} \sum_{k=0}^\infty (\alpha + \beta)^k n = \frac{n}{1 - \alpha - \beta} \ , \end{align*}

Sie sehen hier die Formel für die geometrische Reihe, die anwendbar ist, weil $\alpha + \beta \lt 1$ nach Annahme gilt. Da ein mit $m$ beschrifteter Knoten $cm$ zum Wert von $S(n)$ beiträgt, müssen wir die Summe noch mit $c$ multiplizieren und erhalten

\begin{align*} S(n) & \leq \frac{cn}{1-\alpha-\beta} \ . \end{align*}

In unserem Fall ist $\alpha= \frac{1}{5}$ und $\beta = \frac{7}{10}$ und $c = 3$; somit erhalten wir

\begin{align*} T(n) & \leq \frac{3n}{1 - \frac{1}{5} - \frac{7}{10}} = 30 n \ . \end{align*}

Wenn Ihnen die Rechnung mit Rekursionsbaum ungeheuer ist, können wir einfach per Induktion vorgehen:

Theorem$T(n) \leq C \cdot n$ für einen Wert von $C$, den wir im Beweis bestimmen werden.

Beweis. Wir verwenden Induktion über $n$. Für $n\leq 1$ gilt $T(n) = 0 \leq 30n$. Für $n \geq 2$ rechnen wir:

\begin{align*} T(n) & \leq 3n + T\pfrac{n}{5} + T\pfrac{7n}{10} \\ & \leq 3n + C \cdot \frac{n}{5} + C \cdot \frac{7n}{10} \\ & = 3n + C\cdot n \cdot \frac{9}{10} \ . \end{align*}

Um den Induktionsbeweis zu vollenden, muss dies $\leq Cn$ sein:

\begin{align*} 3n + C\cdot n \cdot \frac{9}{10} & \leq Cn \quad \Longleftrightarrow \\ 3 + \frac{9}{10} \cdot C & \leq C \quad \Longleftrightarrow \\ 3 & \leq \frac{1}{10} \cdot C \quad \Longleftrightarrow \\ C & \geq 30 \ . \end{align*}

Und somit gilt die Aussage des Theorems solange $C \geq 30$, also insbesondere für $C=30$, wie in unserer Rechnung mit dem Rekursionsbaum. \(\square\)