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.
n! = o((n+1)!)c'est-à-dire qu'il pousse strictement plus lentement de manière asymptotique.Réponses:
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)MDans 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))la source
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 quef(x) = O(g(x))si celalim(x->infinity) f(x)/g(x)existe.lim supau lieu delim.x, pas pour toutes les valeurs dex.Un moyen rapide de voir que
n⋅2ⁿc'est plus gros est de faire un changement de variable. Laissezm = 2ⁿ. Ensuiten⋅2ⁿ = ( log₂m )⋅m(en prenant le logarithme de base 2 des deux côtés dem = 2ⁿdonnen = log₂m), et vous pouvez facilement montrer quem log₂mcroît plus vite quem.la source
lg? Logarithme en base 2?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_basesJe suis d'accord que ce
n⋅2ⁿn'est pas le casO(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 dansO(g(n))s'il existe des constantesc > 0etn₀ ≥ 0telles que pour tout ce quen ≥ n₀nous avonsf(n) ≤ c⋅g(n). On peut facilement montrer qu'aucune de ces constantes n'existe pourf(n) = n⋅2ⁿetg(n) = 2ⁿ. Cependant, on peut montrer queg(n)c'est dansO(f(n)).En d'autres termes,
n⋅2ⁿest limité par2ⁿ. 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 ils2ⁿcroissent nécessairement plus lentement quen⋅2ⁿ.la source
f(n) = 2*2^nJe pense que tu voulais diren*2^n?Je ne conteste pas les autres réponses qui disent que cela
n⋅2ⁿpousse plus vite que2ⁿ. Mais lan⋅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 notren⋅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 constantec > 1, quef(x) = O(cx).Car
n⋅2ⁿla constantecpeut être n'importe quel nombre supérieur à2, prenons3. Ensuite:n⋅2ⁿ / 3ⁿ = n ⋅ (2/3)ⁿet c'est moins que1pour toutn.Donc
2ⁿpousse plus lentement quen⋅2ⁿ, le dernier à son tour pousse plus lentement que2.000001ⁿ. Mais tous les trois croissent de façon exponentielle.la source
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.
la source