Bestimmung des Medians

public static int select (int[] S, int k) $\{$
/* Liefert aus dem Feld $S$ das $k$-t kleinste Element. */

     int[] A, B, C;

     int n = |S|;
     if (n < 50) return k-t kleinstes Element per Hand;
     else $\{$
          zerlege S in Gruppen zu je 5 Elementen $S_{1}, S_{2}, \ldots, S_{ \frac{n}{5}}$;
          Bestimme in jeder Gruppe $S_i$ den Median $m_i$;
          Bestimme den Median der Mediane:
               m = select $(\bigcup_{i} m_{i},\frac{n}{10})$;
          A = $\{$x $\in$ S | x < m$\}$;
          B = $\{$x $\in$ S | x == m$\}$;
          C = $\{$x $\in$ S | x > m$\}$;
          if (|A| >= k) return select (A, k);
          if (|A|+|B| >= k) return m;
          if (|A|+|B|+|C| >= k) return select(C, k-|A|-|B|);
     $\}$
$\}$

Beh.:

$\vert A\vert\leq \frac{3}{4} n$

d.h. mind. $\frac{1}{4}$ der Elemente von $S$ ist $\geq m$

$\Rightarrow$ höchstens $\frac{3}{4}$ der Elemente von $S$ ist $< m$

$\Rightarrow \vert A\vert\leq \frac{3}{4} n$, analog $\vert C\vert\leq \frac{3}{4} n$.

Sei $f(n)$ die Anzahl der Schritte, die die Methode select benötigt für eine Menge $S$ der Kardinalität $n$.

Also:

$$f(n)\leq \left\{ \begin{array}{cccccl} c &&&&& \mbox{, f\um... ...\mbox{der Mediane}&&\mbox{A \mbox{ oder }C} \end{array}\right.$$

Beh.:

$f \in O(n)$

Zeige:

$f(n)\leq 20\cdot c \cdot n$

Beweis durch Induktion:

$f(n)\leq c \leq 20 \cdot c \cdot n$ für $n < 50$

Sei bis $n - 1$ bewiesen

$f(n)$	$\leq$	$c\cdot n$	$+$	$f(\frac{n}{5})$	$+$	$f(\frac{3}{4}n)$
	$\uparrow$
	Rekursionsgl.
	$\leq$	$c\cdot n$	$+$	$20 \cdot c \cdot \frac {n}{5}$	$+$	$20\cdot c\cdot \frac{3}{4}\cdot n$
	$\uparrow$
	Ind.-Annahme
	$=$	$1\cdot c\cdot n$	$+$	$4\cdot c\cdot n$	$+$	$15\cdot c\cdot n$
	$=$	$20\cdot c\cdot n$					q.e.d.