-
Data: 2010-05-13 07:59:09
Temat: Re: randomizowany quicksort: analiza dzialania
Od: Mariusz Marszałkowski <m...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]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
Następne wpisy z tego wątku
- 14.05.10 06:02 Maciej Pilichowski
- 14.05.10 22:35 Mariusz Marszałkowski
- 15.05.10 09:36 Maciej Pilichowski
- 15.05.10 09:36 Maciej Pilichowski
Najnowsze wątki z tej grupy
- Can you activate BMW 48V 10Ah Li-Ion battery, connecting to CAN-USB laptop interface ?
- We Wrocławiu ruszyła Odra 5, pierwszy w Polsce komputer kwantowy z nadprzewodzącymi kubitami
- Ada-Europe - AEiC 2025 early registration deadline imminent
- John Carmack twierdzi, że gdyby gry były optymalizowane, to wystarczyły by stare kompy
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2025
- Linuks od wer. 6.15 przestanie wspierać procesory 486 i będzie wymagać min. Pentium
- ,,Polski przemysł jest w stanie agonalnym" - podkreślił dobitnie, wskazując na brak zamówień.
- Rewolucja w debugowaniu!!! SI analizuje zrzuty pamięci systemu M$ Windows!!!
- Brednie w wiki - hasło Dehomag
- Perfidne ataki krakerów z KRLD na skrypciarzy JS i Pajton
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- U nas propagują modę na SI, a w Chinach naukowcy SI po kolei umierają w wieku 40-50lat
- C++. Podróż Po Języku - komentarz
Najnowsze wątki
- 2025-07-07 Re: Ząbki się spaliły jak wiejskie, drewniane stodoły sprzed 50 lat
- 2025-07-06 Kup szybko nową ładowarkę do smartfona
- 2025-07-07 TV z Play (dawniej UPC) -- potrzebny dekoder?
- 2025-07-06 Kup szybko nową ładowarkę do smartfona
- 2025-07-07 mija rok jeżdzenia po lewej
- 2025-07-06 Elektryki jednak są NIEBEZPIECZNE
- 2025-07-08 Fajny film widziałem...
- 2025-07-07 Re: Ząbki się spaliły jak wiejskie, drewniane stodoły sprzed 50 lat
- 2025-07-06 Kup szybko nową ładowarkę do smartfona
- 2025-07-07 Gdańsk => Programista Kotlin <=
- 2025-07-07 Białystok => Mainframe (z/OS, Assembler) Developer <=
- 2025-07-07 Warszawa => Asystent ds. Sprzedaży i Rozwoju Klienta <=
- 2025-07-07 Warszawa => International Freight Forwarder <=
- 2025-07-07 Warszawa => Java Developer <=
- 2025-07-07 Białystok => Software Engineer .Net <=