if (|S| < 50) return k-t kleinstes Element per Hand;
else {
n = |S|;
zerlege S in Gruppen zu je 5 Elementen
S1, S2,..., S;
Bestimme in jeder Gruppe Si den Median mi;
Bestimme den Median der Mediane:
m = select
(mi,
);
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|);
}
}
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:
Beweis durch Induktion:
f (n)c
20 . c . n für n < 50
Sei bis n - 1 bewiesen
f (n) | ![]() |
c . n | + |
f (![]() |
+ |
f (![]() |
|
![]() |
|||||||
Rekursionsgl. | |||||||
![]() |
c . n | + |
20 . c . ![]() |
+ |
20 . c . ![]() |
||
![]() |
|||||||
Ind.-Annahme | |||||||
= | 1 . c . n | + | 4 . c . n | + | 15 . c . n | ||
= | 20 . c . n | q.e.d. |