J'ai remarqué que le big-O de 1000n ou de 10n est la même chose que O(n), mais le big-O de 2^n et de 3^n est différent : O(2^n) et O(3^n), ce que je ne comprends pas, c'est pourquoi ne pouvons-nous pas ignorer les constantes dans ce cas (2 ou 3) et s'il y a une preuve mathématique justifiant cela ?
Réponses
Trop de publicités?
Parce qu'il n'y a pas de valeur constante de k qui satisfait l'inégalité 3^n <= k * 2^n pour des valeurs arbitrairement grandes de n. Ainsi, f(n) = 3^n n'est pas un membre de O(2^n).
Voir http://fr.wikipedia.org/wiki/Notation_grande_O#Famille_des_notations_de_Bachmann%E2%80%93Landau.
Work of Artiz
Points
948
Même si pour la personne qui a posé la question initiale cela pourrait ne plus être utile,
je pense que cela peut être abordé d'une manière plus simple.
Définition de base de la notation O : si f(g) est dans O(g(n)),
alors il existe un nombre rationnel c, pour lequel il est vrai que f(g) = c * g(n), pour n >= n0
(n0 étant un nombre que vous choisissez vous-même)
Essayons d'appliquer cela pour 3^n dans O(2^n)
3^n = 2^n * c
3^n = 2^n * (3^n / 2^n)
3^n = 2^n * (3/2)^n
3^n = 2^n * 1.5^n
cela signifie que c = 1.5^n qui n'est pas un nombre rationnel, mais une fonction exponentielle en soi.
D'autre part, en suivant la même logique pour 3^n dans O(2^n), nous obtiendrions 2^n <= 3^n * (2/3)^n
Cela peut sembler être en conflit, jusqu'à ce que vous réalisiez que 0.75^n < 1 pour tout n > 0, ce qui signifie que si vous prenez n'importe quel c > 1, il sera plus grand que 0.67^n à partir de n = 0
Carlos Villaseñor
Points
11
Pour comparer deux complexités, f(n) et g(n) vous avez appliqué la limite : lim_{n->\inf} f(n)/g(n) et vous avez trois réponses possibles :
1) lim_{n->\inf} f(n)/g(n) = 0; cela implique que f(n) ∈ O(g(n)) et g(n) ∉ O(f(n))
2) lim_{n->\inf} f(n)/g(n) = +/- inf; cela implique que f(n) ∉ O(g(n)) et g(n) ∈ O(f(n))
3) lim_{n->\inf} f(n)/g(n) ∈ Nombre réel; cela implique que f(n) ∈ O(g(n)) et g(n) ∈ O(f(n))
Ensuite, pour démontrer 2^n ∈ O(3^n) vous opérez comme ceci :
lim_{n->\inf} 2^n/3^n = lim_{n->\inf} (2/3)^n = 0
Et c'est démontré, et nous avons également démontré que 3^n ∉ O(2^n), et il est facile de voir que 2/3 < 1 cela fait converger la limite vers 0 donc le résultat de la limite dépend des constantes, je veux dire lim_{n->inf} a^n = 0 si 0 < a < 1 et lim_{n->inf} a^n = inf si a > 1;
Pour une meilleure compréhension, consultez : Introduction to Algorithms, Third Edition Par Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein
Je suis professeur d'algorithmes, j'espère que cela vous a aidé. Prenez soin de vous.
