Re: [obm-l] (O (sqrt n))

[Wendel Scardua <articuno@xxxxxxxxxxxxxxxx>]

Wagner wrote:
> Oi para todos !
> 
> Estava vendo a sequência A006218 no 
> http://www.research.att.com/~njas/sequences/
> e me deparei com O(sqrt(n)) na fórmula da sequência
> Se alguém puder me esclarecer o que isso quer dizer 
> eu agradeceria muito.
> 
> André T.


Essa é a notação 'O grande' (big-oh). A definição é essa:

 f(n) = O(g(n)) se existem c>0 e N>0 tais que

 f(n) <= c . g(n) para todo n > N

Em resumo, é uma espécie de 'limite superior', que dá uma idéia de
como uma função se comporta...
 No caso, O(sqrt(n)) é alguma função complicada, mas certamente menor
do que uma constante vezes raíz de n, a partir de um certo ponto.

 Na verdade f(n) = O(g(n)) é uma 'força de expressão'. O(g(n)) seria
como um 'conjunto' de todas as funções que são <= c.g(n), e está se 
dizendo que f(n) pertence a esse conjunto. 

 Quando usado em uma equação, é como dizer : "existe um f(n) em
O(g(n)) que satisfaz a equação blá-blá-blá"


 Té++

 Wendel Scardua 
--------------------------------------------

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================