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

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

Zwykly quicksort jest solidnie opisany w Cormenie. W skrocie: to
zalezy od danych i wyboru elementu osiowego.

milego dnia, hej

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

do góry

On 11 Maj, 07:41, Maciej Pilichowski
<P...@g...com> wrote:
> On Mon, 10 May 2010 11:52:38 -0700 (PDT), Mariusz Marszałkowski
>
> <m...@g...com> wrote:
> >To ile wykonuje porównań je?li nie n * log(n) ?
>
> Zwykly quicksort
Rozmawiamy o zrandomizowanym quicksorcie.

> jest solidnie opisany w Cormenie.
Cormen podaje właśnie n*log(n)

> W skrocie: to zalezy od danych i wyboru elementu osiowego.
Prawdopodobieństwo istotnego(!) zwiększenia ilosci porownan z
powodu pechowego wyboru elementów osiowych, czyli np. zwiększenia
z n*log(n) do n^2 maleje ze wzrostem liczby sortowanych
elementów przybliżeniu jak 1/n!. Dla dużych N mozna pominac, dla
malych qsorta sie nie stosuje z powodu duzego narzutu liniowego.

W pierwszym poście oczywiście się pomylilem, należy mianownik
zamienić z licznikiem. Oszacowanie prawdopodobienstwa ze para zostanie
porównana wynosi:
ilosc_porownan / ilosc_par => n*log(n) / n*(n-1) => log(n) / (n-1)

Pozdrawiam

do góry

> > <m...@g...com> wrote:
> W pierwszym poście oczywiście się pomylilem, należy mianownik
> zamienić z licznikiem. Oszacowanie prawdopodobienstwa ze para zostanie
> porównana wynosi:
> ilosc_porownan / ilosc_par => n*log(n) / n*(n-1) => log(n) / (n-1)
To "globalnie", dla wszystkich rekurencyjnych wywolan qsorta.

A "lokalnie" (czyli, w jednym wywołaniu rekurencyjnym qsorta) mamy
x danych, czyli x*(x-1) par. Wybieramy osiowy element i porownujemy
go z kazdym elementem, czyli mamy (x-1) porownanych par. Czyli
lokalnie ilosc_porownan / ilosc_par => (x-1) / (x*(x-1)) => 1 / x.

Chyba ze chcesz liczyc prawdopodobienstwo dla kazdej pary
osobno. Ma to sens tylko wtedy gdy odleglosc pomiedzy
para w kolejnych wywolaniach rekurencyjnych sie nie zmienia.

Mamy N elementow. W pierwszym wywolaniu rekurencyjnym
para bedzie porownana z prawdopob. 2/N - element osiowy
musi byc elementem pary. W drugim wywolaniu zeby doszlo
do porownania para nie moze zostac rozbita, czyli element
element osiowy musi nie nalezec do pary ani nie byc
elementem pomiedzy para. Czyli 1 - (odleglosc_pomiedzy_para+2) / N.
Jesli nie dojdzie do podzialu to w drugim wywolaniu mamy
2^2/N szans ze element pary stanie sie elementem osiowym.
Czyli mnozymy (1 - (odleglosc+2) / N) * 2^2/N. W trzecim
analogicznie, ostatecznie trzeba zrobic sume tego szeregu.
Kto zrobi?

Pozdrawiam

do góry

On Tue, 11 May 2010 08:21:34 -0700 (PDT), Mariusz Marszałkowski
<m...@g...com> wrote:

>Jesli nie dojdzie do podzialu to w drugim wywolaniu mamy
>2^2/N szans ze element pary stanie sie elementem osiowym.

Bzdura.

Mariusz, piszesz juz 5 post w tym watku i nawet nie dotarles do
poczatkowego pytania.


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

do góry

On 12 Maj, 08:06, Maciej Pilichowski
<P...@g...com> wrote:
> On Tue, 11 May 2010 08:21:34 -0700 (PDT), Mariusz Marszałkowski
>
> <m...@g...com> wrote:
> >Jesli nie dojdzie do podzialu to w drugim wywolaniu mamy
> >2^2/N szans ze element pary stanie sie elementem osiowym.
>
> Bzdura.

> Mariusz, piszesz juz 5 post w tym watku i nawet nie dotarles do
> poczatkowego pytania.
Jeśli za bzdurę uważasz oczywiste rzeczy to się nie dogadamy :)

Pozdrawiam

do góry

On Wed, 12 May 2010 01:30:16 -0700 (PDT), Mariusz Marszałkowski
<m...@g...com> wrote:

>> >Jesli nie dojdzie do podzialu to w drugim wywolaniu mamy
>> >2^2/N szans ze element pary stanie sie elementem osiowym.
>>
>> Bzdura.
>
>> Mariusz, piszesz juz 5 post w tym watku i nawet nie dotarles do
>> poczatkowego pytania.
>Je?li za bzdurę uważasz oczywiste rzeczy to się nie dogadamy :)

Rozrysuj sobie to na kartce, sam to stwierdzisz.

Puscilem to pytanie na kilku forach, bardziej mi chodzilo o
odtworzenie sposobu myslenia autorow, ale ze wzgledu na zero
odpowiedzi zaczynam liczyc ten wzorek, moze sie okaze, ze sie skraca
do tego co autorzy podali na koncu (wartosc oczekiwana), choc mocno
watpie.

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

do góry

On 13 Maj, 08:12, Maciej Pilichowski
<P...@g...com> wrote:
> On Wed, 12 May 2010 01:30:16 -0700 (PDT), Mariusz Marszałkowski
>
> <m...@g...com> wrote:
> >> >Jesli nie dojdzie do podzialu to w drugim wywolaniu mamy
> >> >2^2/N szans ze element pary stanie sie elementem osiowym.
>
> >> Bzdura.
>
> >> Mariusz, piszesz juz 5 post w tym watku i nawet nie dotarles do
> >> poczatkowego pytania.
> >Je?li za bzdurę uważasz oczywiste rzeczy to się nie dogadamy :)
>
> Rozrysuj sobie to na kartce, sam to stwierdzisz.
Z reguły rozmowy na grupie traktuję rozrywkowo (ale nie olewacko czy
złośliwie),
rozrysowuję sobie w wyobraźni... z różnym efektem. Tym razem chyba z
dobrym. Wybacz że nie zsumowałem tego szeregu, ale nie mam
wprawy i zajęłoby mi to mnóstwo czasu.

Niech mamy N elementów:
E1, E2, E3, E4, E5, ... EN

Wybieramy parę (Ei, Ej) gdzie i<j.
Odległość elementów zdefiniujmy jako {Ex} gdzie i<x<j

Do porównania dojdzie jeśli za element osiowy zostanie
wybrany element Ei lub Ej. Czyli prawdopodobieństwo
że para zostanie porównana wynosi 2/N.

W drugim wywołaniu para może zostać porównana
tylko gdy osiowy element nie należy do Ex. Więc
to prawd. równa się ( |Ex| + 2 ) / N.

Upraszczamy sprawę i zakładamy że w drugim wywołaniu ilość
elementów maleje o połowę.

Czyli szansa porównania drugim wynosi ( 1 - ( |Ex| + 2 ) / N ) * ( 2 /
(N/2) )

Prawdopodobieństwa są rozłączne.
Odległość pomiędzy parą nie zmienia się w kolejnych wywołaniach.

W pierwszym wywołaniu mamy:
2/N
w drugim
( 1 - ( |Ex| + 2 ) / N ) * ( 2^2 / N )
w trzecim
( 1 - ( |Ex| + 2 ) / (N/2) ) * ( 1 - ( |Ex| + 2 ) / N ) * ( 2^3 / N )
w czwartym
( 1 - ( |Ex| + 2 ) / (N/2^2) ) * ( 1 - ( |Ex| + 2 ) / (N/2) ) * ( 1 -
( |Ex| + 2 ) / N ) * ( 2^3 / N )

Niestety nie umiem tego zsumować na szybko.

> Puscilem to pytanie na kilku forach, bardziej mi chodzilo o
Może na matematyce znajdzie się ktoś chętny?

> odtworzenie sposobu myslenia autorow, ale ze wzgledu na zero
> odpowiedzi zaczynam liczyc ten wzorek, moze sie okaze, ze sie skraca
> do tego co autorzy podali na koncu (wartosc oczekiwana), choc mocno
> watpie.
Jeśli autorzy również uprościli że dochodzi do równego podziału i
jeśli się nie rąbnąłem gdzieś to powinno wyjść to samo.

Pozdrawiam

do góry

On Thu, 13 May 2010 00:59:09 -0700 (PDT), Mariusz Marszałkowski
<m...@g...com> wrote:

>Do porównania dojdzie jeśli za element osiowy zostanie
>wybrany element Ei lub Ej. Czyli prawdopodobieństwo
>że para zostanie porównana wynosi 2/N.
>
>W drugim wywołaniu para może zostać porównana
>tylko gdy osiowy element nie należy do Ex. Więc
>to prawd. równa się ( |Ex| + 2 ) / N.
>
>Upraszczamy sprawę i zakładamy że w drugim wywołaniu ilość
>elementów maleje o połowę.
>
>Czyli szansa porównania drugim wynosi ( 1 - ( |Ex| + 2 ) / N ) * ( 2 /
>(N/2) )

Nie rozumiem, dlaczego powyzej (2 akapit) dzielisz przez N (zle), a
tutaj na przykladzie dzielisz przez N/2 (dobrze).

>Niestety nie umiem tego zsumować na szybko.

Tez nie, ale sie juz zdenerwowalem i powalcze ;-)

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

do góry

On 14 Maj, 08:02, Maciej Pilichowski
<P...@g...com> wrote:
> On Thu, 13 May 2010 00:59:09 -0700 (PDT), Mariusz Marszałkowski
>
> <m...@g...com> wrote:
> >Do porównania dojdzie jeśli za element osiowy zostanie
> >wybrany element Ei lub Ej. Czyli prawdopodobieństwo
> >że para zostanie porównana wynosi 2/N.
>
> >W drugim wywołaniu para może zostać porównana
> >tylko gdy osiowy element nie należy do Ex. Więc
> >to prawd. równa się ( |Ex| + 2 ) / N.
>
> >Upraszczamy sprawę i zakładamy że w drugim wywołaniu ilość
> >elementów maleje o połowę.
>
> >Czyli szansa porównania drugim wynosi ( 1 - ( |Ex| + 2 ) / N ) * ( 2 /
> >(N/2) )
>
> Nie rozumiem, dlaczego powyzej (2 akapit) dzielisz przez N (zle), a
> tutaj na przykladzie dzielisz przez N/2 (dobrze).

W powyższym wrzuciłem do licznika mnożenie:
> >Jesli nie dojdzie do podzialu to w drugim wywolaniu mamy
> >2^2/N szans ze element pary stanie sie elementem osiowym.

A w tym do mianownika dzielenie, wychodzi na to samo:
2^2 / N = 2 / (N / 2)

Pozdrawiam

do góry

Mariusz Marszałkowski wrote:

Dobra, porachowalem to juz, ale nadal nie moge dojsc jak autorzy przeszli
nad tymi rachunkami do porzadku i od razu "widzieli" wynik.

Wybor konkretnych elementow nie ma znaczenia, to co ma znaczenie, to
odleglosc miedzy nimi L=j-i+1.

Niech P(N,L) oznacza prawd. porownania tych elementow. N rozmiar sekwencji.

Fakty:
P(N,2) = 1
P(N,L) = 2/N+1/N * ( P(N-1,L)+P(N-2,L)+P(N-3,L)+...+P(L,L) )

Ta suma wyglada paskudnie, ale policzylem na piechote wartosci dla L=3 i N 3
i 4 wynik wychodzil 2/3. Moze przypadek, ale sprawdzilem, czy faktycznie
P(N,L) nie rowna sie 2/L. Tak po prostu.

P(N,L=2) = 1 = 2/2 = 2/L
ok

zalozmy P(N,L) = 2/L

i sprawdzmy:
P(N+1,L) = 2/(N+1) + 1/(N+1) * ( P(N,L) + P(N-1,L)+...+ P(L,L) ) = 2/(N+1) +
(N-L+1)*1/(N+1)*2/L = 2/L

Koniec dowodu.

milego dnia, hej

do góry