On 4 Maj, 10:40, Maciej Pilichowski
<P...@g...com> wrote:
> 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.
>
> Albo o wskazanie literatury, gdzie jest dokladny opis tego algorytmu, a nie
> tylko koncowe wnioski

Jaki to jest dokladny i do czego potrzebny? Mnie wystarcza fakt, ze
zlozonosc jest analogiczna do pola prostokata, gdzie jeden bok to
ilosc elementow, a drugi to logarytm z ilosci elementow.

Dokladna analiza prawdopodobienstwa porownania dwoch elementow
wydaje sie dosc skomplikowana. Do póki dwa elementy nie zostana
od siebie odzielone to istnieje niezerowe prawdopodobienstwo ze
zostana porownane. Gdy dzielimy na pol to (1/2*n)^2 par straci
szanse na porownanie. Gdy dzielimy 1 do (n-1) to wszystkie pary
beda porownane. Ilosc odpadajacych zmian zalezy od tego ktory
co do wielkosci element wybierzemy.

Pozdrawiam



>   Z gory dziekuje!
>
> milego dnia, hej