Pourquoi le journal dans le big-O de la recherche binaire nest-il pas en base 2?

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

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.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *