-
Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed2.atman.pl!newsfeed.atman.pl!.P
OSTED!not-for-mail
From: bartekltg <b...@g...com>
Newsgroups: pl.comp.programming
Subject: Re: Zrandomizowane wyszukiwanie binarne
Date: Tue, 30 Sep 2014 18:58:00 +0200
Organization: ATMAN - ATM S.A.
Lines: 44
Message-ID: <m0enep$3vd$1@node2.news.atman.pl>
References: <5...@g...com>
<m0cm3a$8r6$1@node1.news.atman.pl>
<b...@g...com>
<m0dt2s$6v4$1@node2.news.atman.pl>
NNTP-Posting-Host: 89-73-81-145.dynamic.chello.pl
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: node2.news.atman.pl 1412096281 4077 89.73.81.145 (30 Sep 2014 16:58:01 GMT)
X-Complaints-To: u...@a...pl
NNTP-Posting-Date: Tue, 30 Sep 2014 16:58:01 +0000 (UTC)
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101
Thunderbird/31.1.2
In-Reply-To: <m0dt2s$6v4$1@node2.news.atman.pl>
Xref: news-archive.icm.edu.pl pl.comp.programming:206683
[ ukryj nagłówki ]On 30.09.2014 11:27, bartekltg wrote:
>
> T[L] = 1+sum(i=1,L-1) ro(i,L) [T[i] (i)/L + T[L-i]*(L-i)/L]
Zupełnie już na boku, asymptotycznie to zawsze będzie logarytm.
Przynajmniej jeśli rozkład, z którego
losujemy nie zmienia się, a jedynie go skalujemy.
Wszystkie równania na oczekiwany czas sprowadzają się do postaci
T[L] = \sum_{j=1}^{L-1} w_L[j] T[j] /(L-1)
gdzie wagi (dla każdego L oczywiście inny zestaw)
sumują się do 1. I to jest najistotniejsze tu założenie.
Tak jest w obu przypadkach z poprzednich postów.
W przypadku asymptotycznym sumę zastępujemy całką i mamy
T[L] = 1/L int_0^L w(x/L) T[x] dx
w to waga, zdefiniowana na [0,1]
x=L*y
T[L] = int_0^L w(y) T[y*L] dy
podstawiając za rozwiązanie T[.]=log[.]+C1
int_0^L w(y) (log[y*L] + C1) dy =
int_0^L w(y) log[L] dy + int_0^L w(y) log[y] dy + C2 =
log[L] + C1+C2
No to w domu, bo stałą możemy tak dobrać, by C0 == C1[C0] + C2
pzdr
bartekltg
Następne wpisy z tego wątku
- 30.09.14 23:17 M.M.
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-01 Czy można zaparkować w tym miejscu?
- 2024-05-31 Mały kogenerator gazowy
- 2024-05-30 Co to znaczy wer. eksportowa? Na przykładzie motoru Java 350 Perak
- 2024-05-31 Co to znaczy wer. eksportowa? Na przykładzie motoru Java 350 Perak
- 2024-06-01 karta SD po formacie odzyskiwanie zdjęć i filmów
- 2024-06-01 Modem LTE typu pendrive z agregacją pasm
- 2024-06-01 czy grad zbił wam szybę?
- 2024-06-01 odzysk z panela PV
- 2024-06-01 Sila sygnalu routera
- 2024-06-01 Warszawa => Spedytor międzynarodowy <=
- 2024-06-01 Warszawa => Senior Developer React Native <=
- 2024-06-01 Warszawa => Senior React Native Developer <=
- 2024-06-01 Warszawa => Interactive/Experience Designer <=
- 2024-06-01 Warszawa => Starszy inżynier oprogramowania (Rust) <=
- 2024-06-01 Gdynia => Sales Executive <=