Quelle est la base du logarithme aux fins des algorithmes ?

Question

En considérant O(log(N)) pour la complexité temporelle, quelle est la base du logarithme ?

Answer 1

Tous les logarithmes sont liés par une certaine constante. (D'où la 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.

En général, la base est considérée comme étant 2 lors de la dérivation de l'algorithme. Considérez un tri comme le tri fusion. Vous pouvez construire un arbre à partir de celui-ci, et l'arbre a une hauteur de log₂ n, car chaque nœud a deux branches.

Answer 2

Peu importe, la complexité relative est la même quelle que soit la base utilisée.

Answer 3

Une façon de le penser est que O(log₂X) = O(log₁₀X) = O(log_NX)