[Prévia] [Próxima] [Prévia por assunto] [Próxima por assunto]
[Índice cronológico] [Índice de assunto]

Re: "o" pequeno

Oi Daniel,

Talvez isto possa ajudar:

O(g(n)) = { f(n): existem constantes positivas c e k tais que 0 <= f(n) <= 
cg(n) para todo n >= k }.

o(g(n)) = { f(n): para toda constante c > 0, existe uma constante k > 0 tal 
que 0 <= f(n) < cg(n) para todo n >= k }.

Essas definicoes estao nas paginas 26 e 29 do Introduction to Algorithms - 
Cormen Leiserson e Rivest - MIT Press.

E tambem:

f(n) = O(g(n)) se e somente se |f(n)/g(n)| e' limitada por cima quando n 
tende a infinito.

f(n) = o(g(n)) se e somente se f(n)/g(n) tende a zero quando n tende a 
infinito.

Definicoes encontradas em Analysis of Algorithms - Sedgewick e Flajolet - 
Addison Wesley.

patk


_________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com.