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