8
En considérant O (log (N)) pour la complexité temporelle, quelle est la base de log?Quelle est la base du logarithme aux fins des algorithmes?
A
Répondre
15
Tous les logarithmes sont liés par une constante. (D'où le change-of-base formula). Parce que nous ne tenons généralement pas compte des constantes dans l'analyse de complexité, la base n'a pas d'importance.
Habituellement, la base est considérée comme 2, lors de la dérivation de l'algorithme. Considérez un genre comme merge sort. Vous pouvez en construire un tree, et l'arbre a une hauteur de log₂ n, car chaque nœud a deux branches.
+0
Je voudrais gras face à la deuxième phrase du premier paragraphe ("la base n'a pas d'importance") pour en faire une meilleure réponse. –
10
Peu importe, la complexité relative est la même quelle que soit la base utilisée.
+0
Hmmm. Si vous étendez logiquement cette instruction, vous diriez que O (n^2) est la même complexité relative que O (n^3). –
+0
Pas du tout. Big diff entre 1 million de carrés ou en cubes. Mais log2, log10, log100? Pas beaucoup de différence du tout. – cletus
+0
@Andrew Shepherd - Ce n'est pas correct. log_a (2n)/log_a (n) = log_b (2n)/log_b (n) pour a et b – mob
1
Une façon de penser est que O (log 2 X) = O (log X) = O (log N X)
en double de: http: // stackoverflow. com/questions/1569702/is-big-ologn-log-base-e – outis