está

11

Então, eu tenho esta pergunta para provar uma afirmação:

...O(n)Θ(n)

Eu não preciso saber como provar isso, apenas que, na minha opinião, isso não faz sentido e acho que deveria ser .Θ(n)O(n)

Meu entendimento é que é o conjunto de todas as funções que não fazem pior que n, enquanto Θ ( n ) é o conjunto de todas as funções que não fazem melhor e não é pior que n.O(n)nΘ(n)

Usando isso, posso pensar no exemplo de uma função constante, digamos . Essa função certamente será um elemento de O ( n ), pois não será pior que n, pois n se aproxima de um número suficientemente grande.g(n)=cO(n)nn

No entanto, a mesma função não seria um elemento de Θ ( n ), pois g se sai melhor que n para grandes n ... Então, desde que g O ( n ) e g Θ ( n ) , então O ( n ) q ( n )gΘ(n)nngO(n)gΘ(n)O(n)Θ(n)

Então a pergunta talvez esteja errada? Aprendi que é perigoso fazer essa suposição e, geralmente, perdi alguma coisa, simplesmente não consigo ver o que pode ser nesse caso.

Alguma ideia ? Muito obrigado..

Rawb
fonte
5
f=0f=O(n)fΘ(n)O()
5
Eu acho que você está certo, parece um erro.
Yuval Filmus
3

Respostas:

11

Por sugestão de Rafael, transformei um comentário anterior nesta resposta.

Não é verdade que . De fato, , por definição. Portanto, temos .Θ ( f ( n ) ) = O ( f ( n ) ) ohms ( f ( n ) ) Θ ( f ( n ) ) S ( f ( n ) )O(f(n))Θ(f(n))Θ(f(n))=O(f(n))Ω(f(n))Θ(f(n))O(f(n))

Patrick87
fonte
4

Pense dessa maneira: toda função que "não seja pior que n" e "não seja melhor que n" também é uma função que "não seja pior que n". A parte "não melhor que n" é apenas uma restrição adicional. Esta é uma aplicação direta da regra lógica que diz: . Por esse raciocínio, todas as funções que estão no conjunto também são membros do conjunto .Θ ( n ) O ( n )xyxΘ(n)O(n)

saadtaame
fonte