2 ^ n et n * 2 ^ n sont-ils de la même complexité temporelle?

178

Les ressources que j'ai trouvées sur la complexité temporelle ne sont pas claires sur le moment où il est acceptable d'ignorer les termes d'une équation de complexité temporelle, en particulier avec des exemples non polynomiaux.

Il est clair pour moi que, étant donné quelque chose de la forme n 2 + n + 1, les deux derniers termes sont insignifiants.

Plus précisément, étant donné deux catégorisations, 2 n et n * (2 n ), la seconde est-elle dans le même ordre que la première? La multiplication n supplémentaire a-t-elle de l'importance? Habituellement, les ressources disent simplement que x n est dans une exponentielle et croît beaucoup plus vite ... puis continuez.

Je peux comprendre pourquoi ce ne serait pas le cas puisque 2 n dépasserait considérablement n, mais comme ils ne sont pas additionnés, cela importerait grandement en comparant les deux équations, en fait la différence entre elles sera toujours un facteur de n, ce qui semble pour le moins important.

matty-d
la source
8
À mon avis, étant donné que NLogN est considéré strictement plus lent que N, mais que la plupart des gens ne se soucient pas vraiment de combien, il est prudent de dire que N2 ^ N est simplement plus lent que 2 ^ N, mais pas "assez lent" pour les gens prendre soin ..
Jack
@tobias_k, je comprends ce point, mais considérons l'exemple de O (n!). Un terme n supplémentaire serait-il vraiment différent? O (n!) Est à O (n * n!) Comme O (n!) Est à O ((n + 1)!) Aka le même graphe simplement décalé. La croissance est la même cependant ... Dans ce cas, même si l'une est strictement grande, la croissance est-elle différente? n'est-ce pas ce dont la complexité temporelle se soucie?
matty-d
3
@JackWu mais la plupart des gens ne se soucient pas vraiment de combien jusqu'à ce que vous deviez trier des centaines de millions d'enregistrements avec nlogn au lieu de n :)
CB
4
En fait, n! = o((n+1)!)c'est-à-dire qu'il pousse strictement plus lentement de manière asymptotique.
chepner
16
Notez que cela n'a rien à voir avec la théorie de la complexité, c'est "juste" une question aymptotique. En outre, ce genre de questions est probablement mieux adapté à l' informatique .
Raphaël

Réponses:

231

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

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

Dans le cas de votre question, laissez et laissez . Alors est qui grandira encore à l'infini. N'appartient donc pas à .f(n) = n ⋅ 2ng(n) = 2nf(n)/g(n)nf(n)O(g(n))

Ivaylo Strandjev
la source
5
Pour une définition un peu plus facile à lire, voir ici
Alden
3
Formellement parlant, vous ne pouvez pas prendre la limite de O(f(x)/g(x)); La notification big-O est un raccourci pour un ensemble de fonctions, pas une seule fonction dont vous pouvez limiter la valeur. Cependant, je pense que c'est vrai que vous pouvez montrer que f(x) = O(g(x))si cela lim(x->infinity) f(x)/g(x)existe.
chepner
44
La limite n'a pas à exister; le rapport doit seulement être borné ci-dessus par une constante pour un x suffisamment grand. Par exemple, 2 + sin (x) est dans O (1), mais (2 + sin (x)) / 1 ne s'approche pas d'une limite lorsque x-> infini.
user2357112 prend en charge Monica le
2
La définition serait correcte avec lim supau lieu de lim.
David Eisenstat
11
@IvayloStrandjev veuillez noter que votre brève description est incorrecte. Cela doit être vrai pour une valeur suffisamment grande x, pas pour toutes les valeurs de x.
K.Steff
85

Un moyen rapide de voir que n⋅2ⁿc'est plus gros est de faire un changement de variable. Laissez m = 2ⁿ. Ensuite n⋅2ⁿ = ( log₂m )⋅m(en prenant le logarithme de base 2 des deux côtés de m = 2ⁿdonne n = log₂m), et vous pouvez facilement montrer que m log₂mcroît plus vite que m.

chepner
la source
3
Je vous remercie! C'est la meilleure réponse à mon avis. Les preuves basées sur des définitions formelles sont correctes, mais si vous avez une sorte de pierre d'achoppement à surmonter, une analogie très confortable et familière fera le travail le mieux et le plus rapidement.
John P
1
Question stupide, qu'est-ce que c'est lg? Logarithme en base 2?
Pierre Arlaud
3
C'est une abréviation paresseuse. En informatique, cela a tendance à signifier la base 2 car il résulte principalement de stratégies de division pour conquérir. En notation big-O, cela pourrait représenter n'importe quoi, car le logarithme base-x d'un nombre ne diffère de son logarithme base-y que par un facteur constant, indépendamment de x et y.
chepner le
3
Je devrais noter rétrospectivement qu'il lgs'agit de la notation ISO pour un logarithme en base 10, plutôt que de l'utilisation indépendante de la base la plus couramment utilisée lors de la discussion des temps d'exécution asymptotiques. Voir en.wikipedia.org/wiki/Logarithm#Particular_bases
chepner
D'accord, bien sûr, mais je ne comprends pas pourquoi il est plus évident que m log m croît plus vite que m, plutôt que n 2 ^ n croît plus vite que 2 ^ n.
djechlin
10

Je suis d'accord que ce n⋅2ⁿn'est pas le cas O(2ⁿ), mais j'ai pensé que cela devrait être plus explicite car 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 > 0et n₀ ≥ 0telles que pour tout ce que n ≥ n₀nous avonsf(n) ≤ c⋅g(n) . On peut facilement montrer qu'aucune de ces constantes n'existe pour f(n) = n⋅2ⁿet g(n) = 2ⁿ. Cependant, on peut montrer que g(n)c'est dans O(f(n)).

En d'autres termes, n⋅2ⁿest limité par 2ⁿ. C'est intuitif. Bien qu'ils soient tous les deux exponentiels et qu'il est donc également peu probable qu'ils soient utilisés dans la plupart des circonstances pratiques, nous ne pouvons pas dire qu'ils sont du même ordre car ils 2ⁿcroissent nécessairement plus lentement que n⋅2ⁿ.

zpr
la source
f(n) = 2*2^nJe pense que tu voulais dire n*2^n?
tobias_k
4

Je ne conteste pas les autres réponses qui disent que cela n⋅2ⁿpousse plus vite que 2ⁿ. Mais la n⋅2ⁿcroissance n'est encore qu'exponentielle.

Lorsque nous parlons d'algorithmes, nous disons souvent que l'augmentation de la complexité temporelle est exponentielle. Donc, nous considérons comme 2ⁿ, 3ⁿ, eⁿ, 2.000001ⁿou notre n⋅2ⁿêtre même groupe de complexité avec croissance exponentielle.

Pour lui donner un peu de sens mathématique, on considère qu'une fonction f(x)croît (pas plus vite que) exponentiellement s'il existe une telle constante c > 1, quef(x) = O(cx) .

Car n⋅2ⁿla constante cpeut être n'importe quel nombre supérieur à 2, prenons3 . Ensuite:

n⋅2ⁿ / 3ⁿ = n ⋅ (2/3)ⁿet c'est moins que 1pour toutn .

Donc 2ⁿpousse plus lentement que n⋅2ⁿ, le dernier à son tour pousse plus lentement que 2.000001ⁿ. Mais tous les trois croissent de façon exponentielle.

Andreï
la source
Dans le dernier exemple, n * 2 ^ n est supérieur à 2,000001 ^ n jusqu'à n = 34 726 000. À ce stade, 2 ^ n est un nombre avec plus de 10 millions de chiffres, donc cela n'a pas vraiment d'importance ...
gnasher729
1
@ gnasher729 C'est juste une constante que nous pouvons omettre car f (n) et c * f (n) sont de la même complexité en termes de big-O. par exemple, 40'000'000 * 2.000001 ^ n est supérieur à n * 2 ^ n tout de suite. Mais vous avez raison, cela n'a pas vraiment d'importance, je dirais que cela n'a pas vraiment d'importance une fois que nous atteignons des croissances exponentielles (à moins que nous n'obtenions que de petites valeurs de n).
Andrey
2

Vous avez demandé "le second est-il dans le même ordre que le premier? Est-ce que la multiplication n supplémentaire 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. Voilà la réponse à cette question.

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

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

gnasher729
la source