-
Data: 2010-05-14 22:35:33
Temat: Re: randomizowany quicksort: analiza dzialania
Od: Mariusz Marszałkowski <m...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]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
Następne wpisy z tego wątku
- 15.05.10 09:36 Maciej Pilichowski
- 15.05.10 09:36 Maciej Pilichowski
Najnowsze wątki z tej grupy
- Arch. Prog. Nieuprzywilejowanych w pełnej wer. na nowej s. WWW energokod.pl
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- 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
Najnowsze wątki
- 2025-01-01 Już nie płoną
- 2025-01-01 Digikey, SN74CBT3253CD, FST3253, ktoś ma?
- 2025-01-01 Co tam u Was
- 2025-01-01 Koder szuka pracy. Koduję w j.: Asembler, C, C++ (z bibl. Qt) i D.
- 2025-01-01 Gdańsk => Delphi Programmer <=
- 2025-01-01 Łódź => Programista Full Stack .Net <=
- 2025-01-01 Żerniki => Regionalny Kierownik Sprzedaży (OZE) <=
- 2025-01-01 Wrocław => Specjalista ds. Sprzedaży <=
- 2024-12-31 Warszawa => Spedytor Międzynarodowy <=
- 2024-12-31 Warszawa => Architekt rozwiązań (doświadczenie w obszarze Java, AWS
- 2025-01-01 Przypomnienie: Mini Netykieta polskich grup dyskusyjnych wer. 3.2.2
- 2024-12-31 Zamykanie konta dziecka.
- 2024-12-31 Czy apka bankowa to gra komputerowa?
- 2024-12-31 Szukam: czujnik ruchu z możliwością zaączenia na stałe
- 2024-12-31 Warszawa => Solution Architect (Java background) <=