en considérant O (log (n)) pour la complexité de temps, quelle est la base du journal?
3 Réponses :
Tous les logarithmes sont liés par une certaine constante. (D'où le Formule de changement de base ). Parce que nous ignorons généralement les constantes dans l'analyse de la complexité, la base n'a pas d'importance.
généralement, la base est considérée comme 2, lors de la dérive de l'algorithme. Considérez une sorte comme Fusionner le tri . Vous pouvez construire un arbre en dehors de celui-ci, et l'arbre a une hauteur de log₂ N , car chaque nœud a deux branches.
Je ferais audacil la deuxième phrase du premier paragraphe («la base peu importe») pour en faire une réponse encore meilleure.
Peu importe, la complexité relative est la même quelle que soit la base utilisée.
Hmmm. Si vous étendez logiquement cette déclaration, vous dites que O (n ^ 2) est la même complexité relative que O (n ^ 3).
Pas du tout. Big Diffiff entre 1 million carré ou cubé. Mais log2, log10, log100? Pas beaucoup de différence du tout.
@Andrew Shepherd - Ce n'est pas correct. log_a (2n) / log_a (n) = log_b (2n) / log_b (n) pour tout A et B
@Andres Shepherd: pour développer les autres réponses à votre commentaire, log_a (n) / log_b (n) est une constante qui est la même pour toutes les valeurs de n. Le rapport de (n ^ 2) / (n ^ 3), d'autre part, augmente n grords. L'analyse de la complexité algorithmique concerne la manière dont les exigences en ressources augmentent comme des augmentations n augmentations. Les constantes n'ont pas d'importance. Les valeurs qui varient avec n font.
Un moyen d'y penser est que o (journal 2 x) = O (journal 10 x) = O (log n X)
Dupliquer de: Stackoverflow.com/Questtions/1569702 / is-big-ologn-log-base-e