O que há de errado com as somas dos termos do Landau?

14

eu escrevi

i=1n1i=i=1nO(1)=O(n)

mas meu amigo diz que isso está errado. Na folha de dicas do TCS, eu sei que a soma também é chamada de que tem crescimento logarítmico em . Portanto, meu limite não é muito preciso, mas é suficiente para a análise que eu precisava. nHnn

O que eu fiz errado?

Edit : Meu amigo diz que com o mesmo raciocínio, podemos provar que

i=1ni=i=1nO(1)=O(n)

Agora isso está obviamente errado! O que está acontecendo aqui?

Rafael
fonte
2
Veja uma discussão sobre as tags desta pergunta aqui .
Raphael
meta-discussão sobre os algoritmos de tags .
Kaveh
Veja também um tratamento mais concreto de um exemplo comum: qual é o tempo de execução assintótico desse loop aninhado?
Gilles 'SO- stop be evil'

Respostas:

10

O que você está fazendo é um abuso muito conveniente de notação.

Alguns pedantes dirão que o que você escreve não faz sentido, pois indica um conjunto e você não pode fazer operações aritméticas com eles do jeito que está fazendo.O(f)

Mas é uma boa idéia ignorar esses pedantes e assumir que representa algum membro do conjunto. Então, quando dizemos , o que realmente queremos dizer se . (Nota: alguns pedantes também podem tremer com essa afirmação, alegando que é um número é a função!)f ( n ) = g ( n ) + O ( n ) f ( n ) - g ( n ) O ( n ) f ( n ) fO(f)f(n)=g(n)+O(n)f(n)g(n)O(n)f(n)f

Isso torna muito conveniente escrever expressões como

nk=1nk1/kn+O(n1/3)

O que isso significa é que existe algum tal quefO(n1/3)

nk=1nk1/kn+f(n)

No seu caso de

k=1n1k=k=1nO(1)=O(n)

você está abusando ainda mais e precisa ter cuidado.

Existem duas interpretações possíveis aqui: refere a uma função de ou a uma função de ?n kO(1)nk

Eu acredito que a interpretação correta é interpretá-la como uma função de .k

Se você tentar pensar nisso como uma função de , se considerado incorreto, poderá levar a possíveis falácias, como pensar que é e tentar escreverk O ( 1 ) n k = 1 k = n k = 1 O ( 1 )nkO(1)k=1nk=k=1nO(1)

Se você tentar pensar nisso como uma função de , é verdade que, se (como o argumento vai para ) e nunca for , issof = O ( g ) g 0kf=O(g)g0

S(n)=k=1nf(k)=k=1nO(g(k))=O(k=1n|g(k)|)

Observe que no meio, usamos o conveniente abuso da notação para significar que, para alguma função a soma é . Observe que a função final dentro de se refere a uma função de . A prova não é tão difícil, mas você deve considerar o fato de estar lidando com um limite superior assintótico (ou seja, para argumentos suficientemente grandes), mas a soma começa em .h O ( g ) n k = 1 h ( k ) O n 1O(g(k))hO(g)k=1nh(k)On1

Se você tentar pensar nisso como uma função de , também é verdade que se (como o argumento vai para ), entãof = O ( g ) nf=O(g)

S(n)=k=1nf(k)=k=1nO(g(n))=O(ng(n))

Portanto, sua prova é essencialmente correta, em qualquer uma das interpretações.

Aryabhata
fonte
1
Conclusão: esteja ciente (certifique-se) de que toda ocorrência de um símbolo Landau introduz (tem) sua própria constante .
Raphael
8

O que você escreveu está perfeitamente correto. O th número harmónica é, de facto, o conjunto de .O ( n )nO(n)

Prova: . Eu=1n1Euemn+12n=O(n)

O limite superior não é apertado , mas está correto.O(n)

JeffE
fonte
4
Ok: 1 / i ≤ 1 = O (1).
21412 JeffE
1
A preocupação é direcionada ao segundo sinal de igualdade. Como verifico isso?
Raphael
2
Mas isso também está correto. Uma soma de n termos, cada um dos quais é O (1), é de fato O (n).
Suresh
2
@Suresh Somente se as constantes implícitas no s forem independentes da variável de soma, e esse é o ponto aqui (questão inicial). O
Raphael
2
O bug não está na segunda igualdade. o bug (na segunda expressão) está em como você CHEGA a esse somatório. Indo de está correto. Ele está afirmando que está errado. Sei que isso é óbvio para todos os interessados, mas acho que este é o problema com 'seeding' perguntas :)i = O ( 1 )EuO(1)=O(n)Eu=O(1)
Suresh
6

Para o segundo exemplo, você não pode afirmar que

Eu=O(1)

desde que varia com . Após algumas etapas, será o caso de . Uma maneira mais apropriada é para dizer que uma vez que, de facto, em todo o somatório nunca excede . Por esse raciocínio, n i > n / 2 i = O ( n ) i 1 n n i = 1 i = n i = 1 O ( n ) = n O ( n ) = O ( n 2 )EunEu>n/2Eu=O(n)Eu1n

Eu=1nEu=Eu=1nO(n)=nO(n)=O(n2)

No entanto, a coisa certa a fazer é realmente usar a notação big-O apenas no final. O limite superior limita seu somatório o mais apertado possível, e somente quando terminar, use as notações assintóticas para evitar essas armadilhas.

Tocou.
fonte