Matematické Fórum

JardaB · 17. 10. 2010 16:50

Zdravím,

snažil jsem se toto téma zde vyhledat ale bez úspěchu.

Potřeboval bych poradit jak určit asymptotickou složitost zadané funkce, ale bez použití Master theoremu.

Př. Předpokládejte, že fce je rostoucí a splňuje rovnici $f(n)=2*f(n/2)+n$
a má to vyjít $f(n)=O(n log n)$

Na cviku ukazoval akorát jeden příklad, tak, že si to rozepsal pro f(2^0), f(2^1), f(2^2).... až tam "uviděl" vzorec. Akorát, že ho tam viděl akorát on :)

Neexistuje, prosím, nějaký způsob, který by pochopil normální smrtelník?

Díky moc

Kondr · 20. 10. 2010 21:28

položme $f(2^t)=g(t)$ . Pak máme
$f(2^t)=f(2^{t-1})+2^t$ dosadíme $g$
$g(t)=2g(t-1)+2^t$ posuneme $t$ o 1:
$g(t-1)=2g(t-2)+2^{t-1}$ dvojnásobek této odečteme od předchozí
$g(t)-2g(t-1)=2g(t-1)-4g(t-2)$
$g(t)-4g(t-1)+4g(t-2)=0$
Na řešení takovýchto diferenčních rovnic (tj. lineárních s konstantními koeficienty) máme metody. Říká ti něco charakteristický polynom nebo vytvořující funkce? Pokud ne, je třeba buď napsat prvních 10 hodnot g (protože chceme asymptotické chování, g(1) a g(2) zvolme libovolně) a "uvidět" v tom vzorec (a ten dokázat indukcí), nebo nějakou chytrou substitucí snížit stupeň diferenční rovnice (většinou nelze, zde ano).

Matematické Fórum

#1 17. 10. 2010 16:50

Asymptotické chování fcí

#2 20. 10. 2010 21:28

Re: Asymptotické chování fcí

Zápatí