Matematické Fórum

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?



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).