Por que verdadeiro?

8

3n=2O(n) é aparentemente verdadeiro. Eu pensei que era falso, porque cresce mais rápido do que qualquer função exponencial com uma base de 2.3n

Como verdadeiro?3n=2O(n)

David Faux
fonte
1
Cuidado com o abuso de notação!
Raphael
Realmente não consigo entender o que significa ? primeiro mudei para , depois vi novamente que isso não faz sentido. A pergunta da IMO não faz sentido. 3n=2O(n)3n2O(n)
1
É extremamente comum escrever para o que, no sentido mais estrito, deve ser . Tão comum que dificilmente é considerado abuso de notação. f(x)=O(g(x))f(x)O(g(x))
precisa saber é o seguinte

Respostas:

12

Com alguma álgebra (e alterando a constante no ), podemos realmente mudar as bases.O(n)

3n=(2log23)n=2nlog23

Como é uma constante, . Então .log23nlog23=O(n)3n=2O(n)

Não sei ao certo o que você quer dizer com " cresce mais rápido que qualquer função exponencial com base em 2." claro, mas parece que você quer dizer algo mais geral. Meu palpite é que sua afirmação se aplica a algo como , onde você multiplica a base por uma constante, em oposição a onde você multiplica o número no expoente por uma constante.3n2n=o(3n)O(3n)2O(n)

SamM
fonte
8

3n cresce mais rápido que qualquer função exponencial com uma base de .2

Verdade. Isso implica que não pode ser verdadeiro. Mas o que você tem aqui é .3n=O(2n)2O(n)

Lembre-se de que é realmente um conjunto de funções e, estritamente falando, deveríamos escrever (ou mesmo ). O lado direito não é o exponencial de uma função, mas o exponencial de um conjunto de funções. Expandindo a definição de big oh:O(f(n))3n2O(n)(n3n)2O(nn)

2O(n)=2{fN,p,nN,f(n)pn}={(n2f(n))N,p,nN,f(n)pn}

Como a função exponencial está aumentando, podemos tirar a desigualdade do exponencial:n2n

2O(n)={gN,p,nN,g(n)2pn}

Contraste com

O(2n)={gN,k,nN,g(n)k2n}

Em , a constante multiplicativa está dentro do exponencial. Em , é multiplicado pelo exponencial. , então temos (para qualquer ) , ou seja, podemos usar e , mostrando que .2O(n)O(2n)2pn=2p2nn03n2log232nN=0p=log233n2O(n)

Gilles 'SO- parar de ser mau'
fonte
4

3n=2O(n) é de fato verdade porque, se você recordar a definição de , verá que pode adicionar / multiplicar por qualquer constante. Assim:O(n)

3n<2kn //log2

nlog2(3n)<knlog2(2)

k>log2(3)

Então, como você pode ver, é maior que2kn3nk>log2(3)

Bartosz Przybylski
fonte