Mistrovská věta - příprava

Aplikujeme opět Iterační metodu na "obecnou" rekurenci

Postupně iterujeme (dosazujeme - telescoping), po prvních 3 krocích dostaneme

Tedy po iteracích dostaneme

Iterování skončí po propracování se k , tedy dosažení rovnosti

Výpočtem zjistíme

(případně místo )

Bereme-li , pak dostáváme vztah

  • Pro asymptotiku víme rovnou,

  • Pro je to složitější, protože se vyskytuje i uvnitř sčítanců v sumě, nelze vytknout před sumu!

  • Abychom vystihli celkové chování , je potřeba rozhodnout, který z výrazů je asymptoticky významnější

  • To lze zkoumat pro konkrétní volbu - takto to dělá Iterační metoda

  • Nebo se můžeme omezit na několik kvalitativně odlišných situací, což přesně činí věta dále

Vytvořeno: 29. 11. 2024, 21:40
Poslední aktualizace: 29. 11. 2024, 21:41