-
Data: 2010-05-04 12:55:46
Temat: Re: randomizowany quicksort: analiza dzialania
Od: Mariusz Marszałkowski <m...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]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
Następne wpisy z tego wątku
- 04.05.10 13:47 Maciej Pilichowski
- 04.05.10 14:45 Jan Górski
- 05.05.10 05:41 Maciej Pilichowski
- 05.05.10 17:05 Jan Górski
- 07.05.10 18:38 Mariusz Marszałkowski
- 10.05.10 06:34 Maciej Pilichowski
- 10.05.10 16:21 Jan Górski
- 10.05.10 18:52 Mariusz Marszałkowski
- 11.05.10 05:41 Maciej Pilichowski
- 11.05.10 14:46 Mariusz Marszałkowski
- 11.05.10 15:21 Mariusz Marszałkowski
- 12.05.10 06:06 Maciej Pilichowski
- 12.05.10 08:30 Mariusz Marszałkowski
- 13.05.10 06:12 Maciej Pilichowski
- 13.05.10 07:59 Mariusz Marszałkowski
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-06-27 Re: Prywatny parking? Pierwsze 10 minut bezplatnie
- 2024-06-27 A co mnie to koooorwa obchodzi?
- 2024-06-28 nawigacja satelitarna
- 2024-06-28 SmartLife/Tuya i osuszanie -- mordowanie z zimną krwią...
- 2024-06-27 położyłem kafelki
- 2024-06-28 Łódź => International Freight Forwarder <=
- 2024-06-28 Łódź => Spedytor Międzynarodowy <=
- 2024-06-28 Gdańsk => Head of International Freight Forwarding Department <=
- 2024-06-28 Sopot => Team Leader E-Commerce for Foreign Markets <=
- 2024-06-28 Warszawa => Senior React Native Developer <=
- 2024-06-28 Warszawa => Frontend Developer (React) <=
- 2024-06-28 Warszawa => Software .Net Developer <=
- 2024-06-28 Warszawa => Frontend Developer (React) <=
- 2024-06-28 Warszawa => Programista Full Stack .Net <=
- 2024-06-28 Warszawa => Frontend Developer (React) <=