Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
🔒 23. 3. 2019 Přešli jsme na HTTPS. Prosíme o kontrolu funkčnosti fóra.
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 14. 08. 2017 03:00

kocourOggy
Příspěvky: 30
Pozice: student
Reputace:   
 

binární halda a důkaz časové složitosti - problém se sumou

Zdravím,
zkusím nejdřív napsat sumu, která mi dělá problém, aniž bych předhodil kontext úlohy (třeba je to jen hrátka s indexy, kterou bohužel nevidím). Mám problém přejít přes první rovnítko. Ostatní mi jsou zřejmá, ale přechodu mezi první a druhou sumou nerozumím. Jediné co se mi z toho podařilo vykoukat je, že za i se nejspíš dosadilo i=h-1-j. Jestli ano, proč něco takového můžu udělat?

$\sum_{i=0}^{h-1}  2^{i}\cdot (h-1-i) = \sum_{j=0}^{h-1}  2^{h-1-j}\cdot j = \sum_{j=0}^{h-1}  \frac{2^{h-1}}{ 2^{j}}\cdot j \le n\cdot  \sum_{j=0}^{h-1}  \frac{2^{h-1}}{ 2^{j}}$

Suma se vztahuje k následujícímu důkazu...

Věta: Operace buildHeap má časovou složitost O(n). Uvažujeme min-heap.

Důkaz: Nechť strom má h hladin očíslovaných od 0 (kořen) do h − 1 (listy). Bez újmy na obecnosti budeme předpokládat, že všechny hladiny jsou úplně plné, takže počet prvků haldy je n = 2h − 1.
Jedno BubbleDown na i-té hladině trvá O(h − 1 − i). Pokud to sečteme přes všech 2i vrcholů hladiny a poté přes všechny hladiny, dostaneme (až na konstantu z O): viz suma výše.

Poznámka:
BubbleDown je operace, která prohodí vrchol, který má větší hodnotu v porovnání se svým synem (otec > syn). Tímto posouváme vrchol dolů a operaci prohození otce a syna opakujeme dokud platí podmínka (otec > syn).

Časová složitost BubbleDown na i-té hladině: (2^i)*(h -1-i)
2^i = počet vrcholů na i-té hladině
(h-1-i) = vzdálenost vrcholu od poslední hladiny binární haldy (uvažujeme nejhorší možný případ, tj. kdy vrchol musíme přesunout až do poslední hladiny).

Offline

  • (téma jako vyřešené označil(a) kocourOggy)

#2 14. 08. 2017 14:28

jarrro
Příspěvky: 4961
Škola: UMB BB Matematická analýza
Reputace:   281 
Web
 

Re: binární halda a důkaz časové složitosti - problém se sumou

Súčet je komutatívny čo je v prvej sume nultý člen, je v druhej (h-1)ty člen a naopak


MATH IS THE BEST!!!

Offline

 

#3 14. 08. 2017 15:04

kocourOggy
Příspěvky: 30
Pozice: student
Reputace:   
 

Re: binární halda a důkaz časové složitosti - problém se sumou

↑ jarrro:
Ježiš... to jsou takové maličkosti a já je tam prostě nevidím :/
Děkuju za rychlou odpověď!

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson