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

do góry

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

do góry

On Tue, 4 May 2010 05:55:46 -0700 (PDT), Mariusz Marszałkowski
<m...@g...com> wrote:

> Do póki dwa elementy nie zostana
>od siebie odzielone to istnieje niezerowe prawdopodobienstwo ze
>zostana porownane.

Wiem, ale chodzi mi o konkret, a nie ustalenie faktu, ze to
prawdopodobienstwo jest niezerowe.

milego dnia, hej
Moja wyprzedaz wszystkiego: ksiazki, plyty, filmy.
http://www.garaz.pol.pl/

do góry

>   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.

A to nie jest błąd ? Może prawdopodobieństwo wylosowania wynosi nie "=
2/(j-i+1)" a "=2/(N-i+1)" ?

do góry

On Tue, 4 May 2010 07:45:05 -0700 (PDT), Jan Górski <g...@o...pl>
wrote:

>>   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.
>
>A to nie jest bł?d ? Może prawdopodobieństwo wylosowania wynosi nie "=
>2/(j-i+1)" a "=2/(N-i+1)" ?

a) nie widze z czego wynika podany przez Ciebie wzor ( no i czemu j
jest pominiete, a i nie)

b) nawet jesli to typo w ksiazce, to i tak ten wzor jest zbyt prosty,
bo rozpatruje tylko jeden krok -- i tu nadal nie widze tego, w jaki
sposob mozna je pominac (a skupic sie wylacznie na podzbiorze y)

milego dnia, hej

Moja wyprzedaz wszystkiego: ksiazki, plyty, filmy.
http://www.garaz.pol.pl/

do góry

Jednak wydaje się, że moja sugestia nie jest poprawna. Tak teraz na
spokojnie usiadłem i jednak to nie to.

do góry

On 4 Maj, 15:47, Maciej Pilichowski
<P...@g...com> wrote:
> On Tue, 4 May 2010 05:55:46 -0700 (PDT), Mariusz Marszałkowski
>
> <m...@g...com> wrote:
> > Do póki dwa elementy nie zostana
> >od siebie odzielone to istnieje niezerowe prawdopodobienstwo ze
> >zostana porownane.
>
> Wiem, ale chodzi mi o konkret, a nie ustalenie faktu, ze to
> prawdopodobienstwo jest niezerowe.

Wszystkich par jest N*(N-1)/2. Quicksort wykonuje
N*log(N) porównan. Wiec prawdopodobienstwo ze
para bedzie porownywana wynosi:
(N-1) / ( 2 * log(N) )

Pozdrawiam

do góry

On Fri, 7 May 2010 11:38:57 -0700 (PDT), Mariusz Marszałkowski
<m...@g...com> wrote:

>Quicksort wykonuje
>N*log(N) porównan.

Bzdura.

Dla ustalenia uwagi -- nie interesuja mnie wiesci ludowe, "a mi sie
wydaje", tylko twarde konkrety. Wiec prosze, jesli to mozliwe, nie
pisz juz w tym watku, zwiekszasz tylko stosunek szumu do sygnalu.
Dziekuje.

milego dnia, hej
--
Moja wyprzedaz wszystkiego: ksiazki, plyty, filmy.
http://www.garaz.pol.pl/

do góry

Szukałeś na google z dopiskiem "proof" ? Po polsku jest sporo o
quicksort. Nie mam teraz czasu, żeby pomóc w szukaniu, bo odpowiedzi
chyba nie wymyślę. Jak znajdziesz odpowiedź jednak, to napisz tutaj,
żeby jakoś zakończyć wątek. Powodzenia w szukaniu/mysleniu nad tym.

do góry

On 10 Maj, 08:34, Maciej Pilichowski
<P...@g...com> wrote:
> On Fri, 7 May 2010 11:38:57 -0700 (PDT), Mariusz Marszałkowski
>
> <m...@g...com> wrote:
> >Quicksort wykonuje
> >N*log(N) porównan.
>
> Bzdura

To ile wykonuje porównań jeśli nie n * log(n) ?

do góry