Matematické Fórum

RonFreedom

Ahoj,

mohl by mi prosím někdo pomoci s příkladem 2b, jak ho korektně dokázat?
První jsem zvládl dokázat pomocí limit.
Díky moc.

//forum.matweb.cz/upload3/img/2016-03/86618_V%25C3%25BDst%25C5%2599i%25C5%25BEek.PNG

Freedy · 14. 03. 2016 21:32

Ahoj,

tak třeba to první.
Chceme dokázat implikaci
$f(n)\in o(g(n))\Rightarrow 2^{f(n)}\in o(2^{g(n)})$
Víme tedy, že $\lim_{n\to\infty }\frac{f(n)}{g(n)}=0$ .
Tedy
$\lim_{n\to\infty }\frac{2^{f(n)}}{2^{g(n)}}=\lim_{n\to\infty }2^{f(n)-g(n)}=\lim_{n\to\infty }2^{g(n)\big(\frac{f(n)}{g(n)}-1\big)}$
V exponentu je $g(n)\Big(\frac{f(n)}{g(n)}-1\Big)$ . $\lim_{n\to\infty }g(n)=\infty$ a $\lim_{n\to\infty }\frac{f(n)}{g(n)}-1=-1$ .
Druhé dokážeš analogicky

RonFreedom · 14. 03. 2016 22:00

↑ Freedy:

A nestačí u dvojky vzejít z definice malého o:
Pro všechna C > 0, Existuje n0, tak že pro všechna n >= n0 platí: f(n) < c. g(n)

a říci, že Velké O je jen relaxací u C, kde je jen Existuje C > 0, takže pokud platí o musí i platit O?

Freedy · 14. 03. 2016 22:18

↑ RonFreedom:
Ahoj,
ty ale dokazuješ ze znalosti $f(n)\in o(g(n))$
$2^{f(n)}\in O(2^{g(n)})$ nikoliv $f(n)\in O(g(n))$

RonFreedom · 15. 03. 2016 20:58

↑ Freedy:

ok, takže: $f(n)\in o(g(n))\Rightarrow 2^{f(n)}\in O(2^{g(n)})$

Vím, že: $\lim_{n\to\infty }\frac{f(n)}{g(n)}=0$

Pravá strana implikace: $\lim_{n\to\infty }\frac{2^{f(n)}}{2^{g(n)}}=\lim_{n\to\infty }2^{f(n)-g(n)}=\lim_{n\to\infty }2^{g(n)\big(\frac{f(n)}{g(n)}-1\big)}$

Mohu tedy říci, že tvrzení platí, protože zde již nepožaduji, aby limita výrazu $g(n)\Big(\frac{f(n)}{g(n)}-1\Big)$ se rovnala nule, a mohou nastat jen 2 případy a): $2^{f(n)}\in o(2^{g(n)})$ nebo b) $2^{f(n)}\in \theta(2^{g(n)})$ , čili $2^{f(n)}\in O(2^{g(n)})$

Matematické Fórum

#1 14. 03. 2016 21:17 — Editoval RonFreedom (14. 03. 2016 21:29)

Asym. růst fcí

#2 14. 03. 2016 21:32

Re: Asym. růst fcí

#3 14. 03. 2016 22:00

Re: Asym. růst fcí

#4 14. 03. 2016 22:18

Re: Asym. růst fcí

#5 15. 03. 2016 20:58

Re: Asym. růst fcí

Zápatí