Matematické Fórum

Shalinka

Dobrý den, jen by mě zajímalo, když mám ověřit, že platí nějaká as.složitost. Čemu se musí rovnat limita podílu těch dvou funkcí, aby to platilo? Dejme tomu že tedy máme $f(n)=\Theta (g(n))$ a $\lim_{n\to\infty }=\frac{f(n)}{g(n)}$ .

Je mi jasné, že nebude platit, když bude limita záporná hodnota. Když se bude limita blížit třeba 1 tak asi bude platit, ale co když se bude blížit nekonečnu?

vanok · 14. 12. 2011 18:31

↑ Shalinka:,
Ahoj, je ti tazko odpovedat lebo osobne neviem kto je $\Theta$ .
Medzinarodne povedane ide o nezvykle oznacenie.
Tak prosim napis tu definicui toho pojmu.

Shalinka · 14. 12. 2011 18:43

↑ vanok:
to je theta notace
dá se to napsat i takto
$c1.g(n) <= f(n) <= c2.g(n)$

když
$c1>0, c2>0,n>0$

Shalinka · 15. 12. 2011 00:22

To fakt nikdo neví? :(

Matematické Fórum

#1 14. 12. 2011 17:29 — Editoval Shalinka (14. 12. 2011 18:05)

Asymptotická složitost

#2 14. 12. 2011 18:31

Re: Asymptotická složitost

#3 14. 12. 2011 18:43

Re: Asymptotická složitost

#4 15. 12. 2011 00:22

Re: Asymptotická složitost

Zápatí