2 ^ n e n * 2 ^ n são ao mesmo tempo complexos?

178

Os recursos que encontrei na complexidade do tempo não são claros sobre quando não há problema em ignorar termos em uma equação de complexidade do tempo, especificamente com exemplos não polinomiais.

É claro para mim que, dado algo da forma n 2 + n + 1, os dois últimos termos são insignificantes.

Especificamente, dadas duas categorizações, 2 n e n * (2 n ), o segundo está na mesma ordem que o primeiro? A multiplicação adicional n é importante? Normalmente, os recursos dizem apenas que x n é exponencial e cresce muito mais rápido ... depois siga em frente.

Eu posso entender por que isso não ocorreria, pois 2 n ultrapassará muito n, mas como eles não estão sendo somados, isso importaria muito quando comparadas as duas equações. Na verdade, a diferença entre elas sempre será um fator de n, o que parece importante para dizer o mínimo.

algorithm big-o complexity-theory time-complexity matty-d
fonte
8
Na minha opinião, dado que NLogN é considerado estritamente mais lento que N, mas a maioria das pessoas não se importa com o quanto, é seguro dizer que N2 ^ N é simplesmente mais lento que 2 ^ N, mas não "mais lento o suficiente" para as pessoas se importar .. #
Jack
@tobias_k, eu entendo esse ponto, mas considere o exemplo de O (n!). Um termo extra n seria realmente diferente? O (n!) É O (n * n!) Como O (n!) É O ((n + 1)!), Ou seja, o mesmo gráfico simplesmente mudou. Porém, o crescimento é o mesmo ... Nesse caso, mesmo que um seja estritamente grande, o crescimento é diferente? Não é para isso que a complexidade do tempo se importa?
-matty d
3
@JackWu mas a maioria das pessoas realmente não me importo com o quanto até que você tem que classificar centenas de milhões de registros com nlogn em vez de n :)
CB
4
De fato, n! = o((n+1)!)isto é, cresce estritamente mais lento assintoticamente.
chepner
16
Observe que isso não tem nada a ver com a teoria da complexidade, é "apenas" sobre assintóticos. Além disso, esse tipo de pergunta provavelmente é melhor para a Ciência da Computação .
Raphael

Respostas:

231

Você terá que ir para a definição formal do grande O ( O) para responder a essa pergunta.

A definição é que f(x)pertence a O(g(x))se e somente se o limite existe, ou seja, não é infinito. Em resumo, isso significa que existe uma constante , de modo que o valor de nunca é maior que .limsupx → ∞ (f(x)/g(x))Mf(x)/g(x)M

No caso de sua pergunta, deixe e deixe . Então é o que ainda crescerá infinitamente. Portanto , não pertence a .f(n) = n ⋅ 2ng(n) = 2nf(n)/g(n)nf(n)O(g(n))

Ivaylo Strandjev
fonte
5
Para uma definição um pouco mais fácil de ler, veja aqui
Alden
3
Formalmente falando, você não pode assumir o limite de O(f(x)/g(x)); A notificação big-O é uma abreviação de um conjunto de funções, não uma única função cujo valor você pode limitar. No entanto, acho que é verdade que você pode mostrar isso, f(x) = O(g(x))se lim(x->infinity) f(x)/g(x)existir.
13134 chepner
44
O limite não precisa existir; a razão apenas deve ser delimitada acima por uma constante para x suficientemente grande. Por exemplo, 2 + sin (x) está em O (1), mas (2 + sin (x)) / 1 não se aproxima de um limite como x-> infinito.
user2357112 suporta Monica
2
A definição estaria correta com em lim supvez de lim.
David Eisenstat
11
@IvayloStrandjev, observe que sua descrição resumida está incorreta. Isso deve ser verdadeiro para um valor suficientemente grande x, não para todos os valores de x.
K.Steff
85

Uma maneira rápida de ver que n⋅2ⁿé maior é fazer uma alteração de variável. Let m = 2ⁿ. Então n⋅2ⁿ = ( log₂m )⋅m(usando o logaritmo de base 2 em ambos os lados da m = 2ⁿdoação n = log₂m), e você pode mostrar facilmente que m log₂mcresce mais rápido que m.

chepner
fonte
3
Obrigado! Esta é a melhor resposta na minha opinião. As provas baseadas em definições formais estão corretas, mas se você tiver algum obstáculo para superar, uma analogia muito confortável e familiar fará o trabalho da melhor e mais rápida.
John P
1
Pergunta estúpida, o que é lg? Logaritmo na base 2?
Pierre Arlaud 14/02
3
É uma abreviação preguiçosa. Na ciência da computação, tende a significar a base 2 porque resulta principalmente de estratégias de dividir e conquistar. Na notação big-O, poderia representar qualquer coisa, porque o logaritmo base-x de um número difere do logaritmo base-y por apenas um fator constante, independentemente de x e y.
chepner
3
Devo observar em retrospecto que lgé a notação ISO para um logaritmo de base 10, em vez do uso agnóstico de base mais comumente usado ao discutir tempos de execução assintóticos. Veja en.wikipedia.org/wiki/Logarithm#Particular_bases
chepner
Ok, claro, mas não entendo por que é mais óbvio que m log m cresce mais rápido que m, do que n 2 ^ n cresce mais rápido que 2 ^ n.
djechlin
10

Concordo que n⋅2ⁿnão está presente O(2ⁿ), mas achei que deveria ser mais explícito, pois o limite de uso superior nem sempre é válido.

Pela definição formal de Big-O: f(n)está em O(g(n))se existem constantes c > 0e n₀ ≥ 0tais que, por tudo n ≥ n₀que temos f(n) ≤ c⋅g(n). É fácil mostrar que essas constantes não existem para f(n) = n⋅2ⁿe g(n) = 2ⁿ. No entanto, pode ser demonstrado que g(n)está emO(f(n)) .

Em outras palavras, n⋅2ⁿé mais baixo delimitado por 2ⁿ. Isso é intuitivo. Embora ambos sejam exponenciais e, portanto, sejam igualmente improváveis ​​de serem usados ​​na maioria das circunstâncias práticas, não podemos dizer que eles são da mesma ordem, porque 2ⁿnecessariamente crescem mais lentamente que n⋅2ⁿ.

zpr
fonte
f(n) = 2*2^nEu acho que você quis dizer n*2^n?
Tobias_k 14/02
4

Eu não discuto com outras respostas que dizem que n⋅2ⁿcresce mais rápido que 2ⁿ. Mas n⋅2ⁿcresce ainda é apenas exponencial.

Quando falamos de algoritmos, costumamos dizer que a complexidade do tempo cresce é exponencial. Então, nós consideramos ser 2ⁿ, 3ⁿ, eⁿ, 2.000001ⁿ, ou o nosso n⋅2ⁿser mesmo grupo de complexidade com exponencial cresce.

Para dar um pouco de sentido matemático, consideramos uma função f(x)crescer (não mais rápido que) exponencialmente se existe uma constante c > 1tão grande .f(x) = O(cx)

Pois n⋅2ⁿa constante cpode ser qualquer número maior que 2, vamos pegar 3. Então:

n⋅2ⁿ / 3ⁿ = n ⋅ (2/3)ⁿe isso é menor do que 1para qualquern .

Então 2ⁿcresce mais devagar que n⋅2ⁿ, o último, por sua vez, cresce mais devagar que 2.000001ⁿ. Mas todos os três crescem exponencialmente.

Andrey
fonte
No último exemplo, n * 2 ^ n é maior que 2.000001 ^ n até n = 34.726.000. Nesse ponto 2 ^ n é um número com mais de 10 milhões de dígitos, por isso realmente não importa ...
gnasher729
1
@ gnasher729 É apenas uma constante que podemos omitir, pois f (n) ec * f (n) é a mesma complexidade em termos de big-O. por exemplo, 40'000'000 * 2.000001 ^ n é maior que n * 2 ^ n imediatamente. Mas você está certo, isso realmente não importa, eu diria que realmente não importa uma vez que atingimos um crescimento exponencial (a menos que obtenhamos apenas pequenos valores de n).
Andrey
2

Você perguntou "o segundo está na mesma ordem que o primeiro? A multiplicação adicional n é importante?" Estas são duas perguntas diferentes, com duas respostas diferentes.

n 2 ^ n cresce assintoticamente mais rápido que 2 ^ n. Essa é a pergunta respondida.

Mas você poderia perguntar "se o algoritmo A leva 2 ^ n nanossegundos e o algoritmo B leva n 2 ^ n nanossegundos, qual é o maior n onde eu posso encontrar uma solução em um segundo / minuto / hora / dia / mês / ano / ano? E as respostas são n = 29/35/41/46/51/54 vs. 25/30/36/40/45/49 Não há muita diferença na prática.

O tamanho do maior problema que pode ser resolvido no tempo T é O (ln T) nos dois casos.

gnasher729
fonte