Hej,

Czytam opis randomizowanego quicksorta (Metody probabilistyczne i
obliczenia, Michael Mitzenmacher , E. Upfal) i nie moge dojsc jak
autorzy doszli do pewnego wniosku.
Chodzi o obliczenie prawd. ze dwa elementy beda ze soba porownane.

Na wejsciu mamy posortowana liste y (y1,..yN) i wybieramy z niej
losowo element osiowy. Pytamy o prawd. porownania elementow yi i yj
gdzie j>i.

Wg autorow = 2/(j-i+1) i podaja na dowod tego bardzo prosty wniosek
-- element yi lub yj musi byc wybrany w pierwszym podejsciu z
podzbioru yi,yi+1,..yj-1,yj.

Zebym nie wiem jak na to patrzyl nie moge dojsc do tego samego
wniosku -- wg mnie mozna wybrac w pierwszym podejsciu element np. yh
(i>h), a w drugim yi co bedzie skutkowalo porownaniem yi i yj. Innymi
slowy autorzy pomijaja prawdopodobienstwo redukcji pelnego zbioru y do
podzbioru do yi...yj, a przeciez to nie jest pewnik.

Prosze o oswiecenie mnie :-) Albo o wskazanie literatury, gdzie jest
dokladny opis tego algorytmu, a nie tylko koncowe wnioski (Knuth: nic
nie znalazlem, Cormen -- tylko ogolne oszacowanie).

Z gory dziekuje!

milego dnia, hej