Est-ce que 2 ^ n et n * 2 ^ n sont dans la même complexité de temps?

Les ressources que j’ai trouvées sur la complexité temporelle ne sont pas claires sur le moment opportun pour ignorer les termes dans une équation de complexité temporelle, en particulier avec des exemples non polynomiaux.

Il est clair pour moi que compte tenu de la forme n 2 + n + 1, les deux derniers termes sont insignifiants.

Spécifiquement, étant donné deux catégorisations, 2 n et n * (2 n ), le second est-il dans le même ordre que le premier? Est-ce que la multiplication supplémentaire n est importante? Habituellement, les ressources indiquent simplement que x n est exponentielle et croît beaucoup plus rapidement … puis continuez.

Je peux comprendre pourquoi ce ne serait pas le cas puisque 2 n va grandement dépasser n, mais comme ils ne sont pas additionnés, il serait très important de comparer les deux équations, en fait la différence entre eux sera toujours un facteur de n, ce qui semble important pour le moins qu’on puisse dire.

Vous devrez aller à la définition formelle du grand O ( O ) pour répondre à cette question.

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

Dans le cas de votre question, laissez f(n) = n ⋅ 2 n et laissez g(n) = 2 n . Alors f(n)/g(n) est n qui grandira toujours à l’infini. Par conséquent, f(n) n’appartient pas à O(g(n)) .

Un moyen rapide de voir que n⋅2ⁿ est plus grand consiste à modifier la variable. Soit m = 2ⁿ . Alors n⋅2ⁿ = ( log₂m )⋅m (en prenant le logarithme base 2 des deux côtés de m = 2ⁿ donne n = log₂m ), et vous pouvez facilement montrer que m log₂m croît plus vite que m .

Je suis d’accord que n⋅2ⁿ n’est pas dans O(2ⁿ) , mais j’ai pensé qu’il devrait être plus explicite puisque la limite d’utilisation supérieure ne tient pas toujours.

Par la définition formelle de Big-O: f(n) est dans O(g(n)) s’il existe des constantes c > 0 et n₀ ≥ 0 telles que pour tout n ≥ n₀ on ait f(n) ≤ c⋅g(n) . On peut facilement montrer qu’il n’existe pas de telles constantes pour f(n) = n⋅2ⁿ et g(n) = 2ⁿ . Cependant, on peut montrer que g(n) est dans O(f(n)) .

En d’autres termes, n⋅2ⁿ est inférieur à 2ⁿ . Ceci est intuitif. Bien qu’ils soient tous deux exponentiels et donc peu susceptibles d’être utilisés dans la plupart des cas, nous ne pouvons pas dire qu’ils sont du même ordre car 2ⁿ croît nécessairement plus lentement que n⋅2ⁿ .

Je ne discute pas avec d’autres réponses qui disent que n⋅2ⁿ croît plus vite que 2ⁿ . Mais n⋅2ⁿ croître.

Lorsque nous parlons d’algorithmes, nous disons souvent que la complexité du temps augmente de manière exponentielle. Donc, nous considérons être 2ⁿ , 3ⁿ , eⁿ , 2.000001ⁿ , ou notre n⋅2ⁿ être le même groupe de complexité avec une croissance exponentielle.

Pour lui donner un sens mathématique, nous considérons qu’une fonction f(x) croît (pas plus vite que) de manière exponentielle s’il existe une telle constante c > 1 , que f(x) = O(c x ) .

Pour n⋅2ⁿ la constante c peut être n’importe quel nombre supérieur à 2 , prenons 3 . Alors:

n⋅2ⁿ / 3ⁿ = n ⋅ (2/3)ⁿ et ceci est inférieur à 1 pour n quelconque.

Donc 2ⁿ croît plus lentement que n⋅2ⁿ , le dernier devient plus lent que 2.000001ⁿ . Mais tous les trois croissent de manière exponentielle.

Vous avez demandé “est le deuxième dans le même ordre que le premier? Est-ce que la multiplication supplémentaire n est importante?” Ce sont deux questions différentes avec deux réponses différentes.

n 2 ^ n croît asymptotiquement plus vite que 2 ^ n. C’est la question à laquelle j’ai répondu.

Mais vous pourriez demander “si l’algorithme A prend 2 ^ n nanosecondes, et que l’algorithme B prend n 2 ^ n nanosecondes, quel est le plus grand n où je peux trouver une solution dans une seconde / minute / heure / jour / mois / année? 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 gros problème pouvant être résolu avec le temps T est O (ln T) dans les deux cas.