eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingrandomizowany quicksort: analiza dzialaniaRe: randomizowany quicksort: analiza dzialania
  • Path: news-archive.icm.edu.pl!news.rmf.pl!nf1.ipartners.pl!ipartners.pl!plix.pl!newsf
    eed1.plix.pl!news-out2.kabelfoon.nl!newsfeed.kabelfoon.nl!bandi.nntp.kabelfoon.
    nl!feeder.news-service.com!postnews.google.com!37g2000yqm.googlegroups.com!not-
    for-mail
    From: Mariusz Marszałkowski <m...@g...com>
    Newsgroups: pl.comp.programming
    Subject: Re: randomizowany quicksort: analiza dzialania
    Date: Thu, 13 May 2010 00:59:09 -0700 (PDT)
    Organization: http://groups.google.com
    Lines: 74
    Message-ID: <7...@3...googlegroups.com>
    References: <4...@o...googlegroups.com>
    <u...@4...com>
    <4...@k...googlegroups.com>
    <n...@4...com>
    <a...@e...googlegroups.com>
    <c...@p...googlegroups.com>
    <a...@4...com>
    <f...@i...googlegroups.com>
    <8...@4...com>
    NNTP-Posting-Host: 89.229.34.123
    Mime-Version: 1.0
    Content-Type: text/plain; charset=UTF-8
    Content-Transfer-Encoding: quoted-printable
    X-Trace: posting.google.com 1273737550 13060 127.0.0.1 (13 May 2010 07:59:10 GMT)
    X-Complaints-To: g...@g...com
    NNTP-Posting-Date: Thu, 13 May 2010 07:59:10 +0000 (UTC)
    Complaints-To: g...@g...com
    Injection-Info: 37g2000yqm.googlegroups.com; posting-host=89.229.34.123;
    posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj
    User-Agent: G2/1.0
    X-HTTP-UserAgent: Mozilla/5.0 (Windows; U; Windows NT 5.1; pl; rv:1.9.2.3)
    Gecko/20100401 Firefox/3.6.3 (.NET CLR 3.5.30729),gzip(gfe)
    Xref: news-archive.icm.edu.pl pl.comp.programming:185565
    [ ukryj 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

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: