2 ^ n et n * 2 ^ n dans la même complexité de temps ?

Question

Les ressources que j'ai trouvé sur le temps de la complexité ne sont pas claires quand il est ok pour ignorer les conditions dans un temps de la complexité de l'équation, en particulier avec les non-polynomial exemples.

Il est clair pour moi que quelque chose de la forme n² + n + 1, les deux derniers termes sont négligeables.

Plus précisément, compte tenu de deux catégorisations, 2ⁿ, et n*(2ⁿ), est le deuxième dans le même ordre que la première? L'n de multiplication-il question? Habituellement, les ressources viens de dire xⁿ est une exponentielle et se développe beaucoup plus vite... puis s'en vont.

Je peux comprendre pourquoi il ne serait pas depuis 2ⁿ va largement dépasser la n, mais parce qu'ils ne sont pas ajoutés ensemble, il importe grandement lorsque l'on compare les deux équations, en fait, la différence entre eux sera toujours un facteur de n, ce qui semble important, pour dire le moins.

Merci d'avance pour votre aide!

Answer 1

Vous devrez vous rendre à la définition formelle de la grande-oh(O) afin de répondre à cette question.

La définition est que l' f(x) appartient O(g(x)) si et seulement si la limite limsup(x->infinity) (f(x)/g(x)) existe c'est à dire n'est pas infini. En bref, cela signifie qu'il existe une constante M telle que la valeur de f(x)/g(x) n'est jamais plus grand que M.

Dans le cas de votre question, permettez - f(n) = n * 2n et laissez - g(n) = 2n. Ensuite, f(n)/g(n) est n qui va encore s'agrandir à l'infini. Par conséquent, f(n) n'appartient pas à l' O(g(n)).

Answer 2

Un moyen rapide de voir qu' n*2^n est plus important est de faire un changement de variable. Laissez - m = 2^n. Ensuite, n*2^n = (log2m)*m (en prenant log sur les deux côtés de l' m = 2^n sur la base de 2 donne n = log2m ), et vous pouvez facilement montrer qu' m log2m augmente plus rapidement que l' m.

Answer 3

Je suis d'accord qu' n*2^n n'est pas en O(2^n), mais j'ai pensé qu'il devrait être plus explicite car la limite supérieure d'utilisation n'est pas toujours tenir.

Par la définition officielle de Big-O: f(n) est O(g(n)) s'il existe des constantes c > 0 et n0>= 0 tel que pour tout n >= n0 nous avons f(n) <= c*g(n). Il peut facilement être démontré que ces constantes existent pour f(n) = n*2^n et g(n) = 2^n. Cependant, il peut être démontré que, d' g(n) est O(f(n)).

En d'autres termes, n*2^n est inférieure délimitée par 2^n. C'est intuitive. Bien qu'ils sont à la fois exponentielle et sont donc tout aussi peu de chances d'être utilisé dans la plupart des circonstances, on ne peut pas dire qu'ils sont du même ordre, car 2^n nécessairement se développe plus lentement que n*2^n.

Answer 4

Je ne discute pas avec les autres réponses qui disent que c' n*2^n augmente plus rapidement que l' 2^n. Mais n*2^n pousse est encore qu'exponentielle.

Quand on parle d'algorithmes, on dit souvent que le temps de la complexité croît de façon exponentielle. Donc, nous considérons 2^n, 3^n, e^n, 2.000001^n, ou de notre - n*2^n à être d'un même groupe de complexité exponentielle avec de pousse.

Pour donner un peu de sens mathématique, nous considérons une fonction f(x) de croître (pas plus rapide que) de façon exponentielle si il existe une telle constante c > 1, f(x) = O(c^x).

Pour n*2^n la constante c peut être n'importe quel nombre supérieur à 2, prenons 3. Alors:

n*2^n / 3^n = n * (2/3)^n et c'est moins de la 1 pour toute n.

Donc, 2^n se développe plus lentement que n*2^n, la dernière, à son tour, se développe plus lentement que 2.000001^n. Mais tous les trois d'entre eux croître de façon exponentielle.

Answer 5

Vous avez demandé "est le deuxième dans le même ordre que la première? L'n de multiplication-il question?" Ce sont deux questions différentes, avec deux réponses différentes.

n 2^n augmente asymptotiquement plus rapide que 2^n. C'est que la réponse à la question.

Mais vous pourriez demander "si l'algorithme A prend 2^n nanosecondes, et de l'algorithme B prend n 2^n nanosecondes, ce qui est le plus grand n, où je peux trouver une solution dans une seconde / minute / heure / jour / mois / année? Et les réponses sont n = 29/35/41/46/51/54 vs 25/30/36/40/45/49. Pas beaucoup de différence dans la pratique.

La taille du plus grand problème qui peut être résolu dans le temps T est O (ln T) dans les deux cas.