eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingrandomizowany quicksort: analiza dzialaniaRe: randomizowany quicksort: analiza dzialania
  • Path: news-archive.icm.edu.pl!news.gazeta.pl!newsfeed.pionier.net.pl!news.internetia.
    pl!not-for-mail
    From: Maciej Pilichowski <b...@S...FM>
    Newsgroups: pl.comp.programming
    Subject: Re: randomizowany quicksort: analiza dzialania
    Followup-To: pl.comp.programming
    Date: Sat, 15 May 2010 11:36:51 +0200
    Organization: Netia S.A.
    Lines: 30
    Message-ID: <hslpu7$dql$1@mx1.internetia.pl>
    References: <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>
    <7...@3...googlegroups.com>
    <t...@4...com>
    <6...@u...googlegroups.com>
    NNTP-Posting-Host: 77-253-60-136.adsl.inetia.pl
    Mime-Version: 1.0
    Content-Type: text/plain; charset="UTF-8"
    Content-Transfer-Encoding: 8Bit
    X-Trace: mx1.internetia.pl 1273916167 14165 77.253.60.136 (15 May 2010 09:36:07 GMT)
    X-Complaints-To: a...@i...pl
    NNTP-Posting-Date: Sat, 15 May 2010 09:36:07 +0000 (UTC)
    X-Tech-Contact: u...@i...pl
    User-Agent: KNode/4.4.3
    X-Server-Info: http://www.internetia.pl/news/
    Xref: news-archive.icm.edu.pl pl.comp.programming:185574
    [ ukryj nagłówki ]

    Mariusz Marszałkowski wrote:

    Dobra, porachowalem to juz, ale nadal nie moge dojsc jak autorzy przeszli
    nad tymi rachunkami do porzadku i od razu "widzieli" wynik.

    Wybor konkretnych elementow nie ma znaczenia, to co ma znaczenie, to
    odleglosc miedzy nimi L=j-i+1.

    Niech P(N,L) oznacza prawd. porownania tych elementow. N rozmiar sekwencji.

    Fakty:
    P(N,2) = 1
    P(N,L) = 2/N+1/N * ( P(N-1,L)+P(N-2,L)+P(N-3,L)+...+P(L,L) )

    Ta suma wyglada paskudnie, ale policzylem na piechote wartosci dla L=3 i N 3
    i 4 wynik wychodzil 2/3. Moze przypadek, ale sprawdzilem, czy faktycznie
    P(N,L) nie rowna sie 2/L. Tak po prostu.

    P(N,L=2) = 1 = 2/2 = 2/L
    ok

    zalozmy P(N,L) = 2/L

    i sprawdzmy:
    P(N+1,L) = 2/(N+1) + 1/(N+1) * ( P(N,L) + P(N-1,L)+...+ P(L,L) ) = 2/(N+1) +
    (N-L+1)*1/(N+1)*2/L = 2/L

    Koniec dowodu.

    milego dnia, hej

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: