Je suis nouveau dans la compréhension des algorithmes informatiques. Je comprends le processus de la recherche binaire, mais jai un léger malentendu sur son efficacité.
Dans une taille de $ s = 2 ^ n $ éléments, il faudrait, en moyenne, $ n $ étapes pour trouver un élément particulier. Prendre le logarithme de base 2 des deux côtés donne $ \ log_2 (s) = n $. Le nombre moyen d’étapes de l’algorithme de recherche binaire ne serait-il donc pas $ \ log_2 (s) $?
Cet article de Wikipedia sur lalgorithme de recherche binaire dit que la performance moyenne est $ O (\ log n) $. Pourquoi est-ce ainsi? Pourquoi ce nombre nest-il pas $ \ log_2 (n) $?
Commentaires
- Dupliquer sur SO – La base du journal Big O (logn) est-elle e?
Réponse
Lorsque vous modifiez la base du logarithme, lexpression résultante ne diffère que par un facteur constant qui, de définition de la notation Big-O , implique que les deux fonctions appartiennent à la même classe en ce qui concerne leur comportement asymptotique.
Par exemple $$ \ log_ {10} n = \ frac {\ log_ {2} n} {\ log_ {2} 10} = C \ log_ {2} {n} $$ où $ C = \ frac {1} {\ log_ {2} 10} $.
Donc $ \ log_ {10} n $ et $ \ log_ {2} n $ diffèrent par une constante $ C $, et par conséquent les deux sont vrais: $$ \ log_ {10} n \ text {is} O (\ log_ {2} n) $$ $$ \ log_ {2} n \ text {is} O (\ log_ {10} n) $$ En général $ \ log_ {a} {n} $ est $ O (\ log_ {b} {n}) $ pour les entiers positifs $ a $ et $ b $ supérieurs à 1.
Un autre fait intéressant avec les fonctions logarithmiques est que tandis que pour la constante $ k > 1 $, $ n ^ k $ nest PAS $ O (n) $, mais $ \ log {n ^ k} $ est $ O (\ log {n}) $ puisque $ \ log {n ^ k} = k \ log {n} $ qui diffère de $ \ log {n} $ uniquement par un facteur constant $ k $.
Commentaires
- Pas seulement pour les entiers positifs: pour tous les vrais $ a, b > 1 $, par exemple $ e $.
- Jajouterais que cest la raison pour laquelle avec la notation big-O, la base du logarithme nest généralement pas spécifiée. Cela signifie également quil ny a aucune confusion sur la base utilisée par $ O (\ log n) $: il peut sagir de lune des bases couramment utilisées, car elle ne fait ' aucune différence.
Réponse
En plus de la réponse de fade2black (qui est tout à fait correcte), il est intéressant de noter que la notation « $ \ log (n) $ » est ambiguë. La base nest pas réellement spécifiée et la base par défaut change en fonction du contexte. En mathématiques pures, la base est presque toujours supposée être $ e $ (sauf indication contraire), alors que dans certains contextes dingénierie, elle peut être 10. En informatique , la base 2 est tellement omniprésente que $ \ log $ est souvent supposé être la base 2. Cet article de wikipedia ne dit jamais rien sur la base.
Mais, comme cela a déjà été montré, dans ce cas il ne le fait pas » t finissent par être important.
Commentaires
- Il est probablement intéressant de noter que si " log (n) " peut être ambigu que " O (log (n)) " ce nest pas parce que ce dernier na quune seule signification, quelle que soit la base à laquelle vous pensez.