Bestimmung des Medians

static double select (Menge S, int k) {
/* Liefert aus der Menge S das k -t kleinste Element. */
/* Die Menge S habe n Elemente. k n . */
     Menge A, B, C;

     if (|S| < 50) return k-t kleinstes Element per Hand;
     else {
          n = |S|;
          zerlege S in Gruppen zu je 5 Elementen S₁,S₂,...,S ;
          Bestimme in jeder Gruppe S_i den Median m_i ;
          Bestimme den Median der Mediane:
               m = select (m_i,) ;
          A = { x S | x < m } ;
          B = { x S | x == m } ;
          C = { x S | x > m } ;
          if (|A| >= k) return select (A, k);
          else if (|A|+|B| >= k) return m;
          else /* if (|A|+|B|+|C| >= k) */ return select(C, k-|A|-|B|);
     }
}

Beh.:

|A| n

d.h. mind. der Elemente von S ist m

höchstens der Elemente von S ist < m

|A| n , analog |C| 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)

Beh.:

f O(n)

Zeige:

f (n) 20 · c · n

Beweis durch Induktion:

f (n) c 20 · c · n für n < 50

Sei bis n - 1 bewiesen

f (n) c · n + + Rekursionsgl.

c · n + + Ind.-Annahme

= 1 · c · n + 4 · c · n + 15 · c · n

= 20 · c · n q.e.d.