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

35

Je suis novice dans la compréhension des algorithmes informatiques. Je comprends le processus de recherche binaire, mais j'ai un léger malentendu avec son efficacité.

Dans une taille de éléments, il faudrait en moyenne étapes pour trouver un élément particulier. En prenant le logarithme en base 2 des deux côtés, on obtient . Donc, le nombre moyen d'étapes pour l'algorithme de recherche binaire ne serait-il pas ? n log 2 ( s ) = n log 2 ( s )s=2nnlog2(s)=nlog2(s)

Cet article de Wikipedia sur l'algorithme de recherche binaire indique que la performance moyenne est de . Pourquoi cela est-il ainsi? Pourquoi ce numéro n'est-il pas ?log 2 ( n )O(logn)log2(n)

Dr Pepper
la source
2
Dupliquer sur SO - Big O (logn) est-il basé sur le journal?
Dukeling

Réponses:

86

Lorsque vous modifiez la base du logarithme, l'expression résultante ne diffère que par un facteur constant qui, par 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, où .C=1

log10n=log2nlog210=Clog2n
C=1log210

Ainsi, et diffèrent par une constante et sont donc vrais tous les deux: vrai \ 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.log 2 n C log 10 n  est  O ( log 2 n ) log 2 n  est  O ( log 10 n ) log alog10nlog2nC

log10n is O(log2n)
log2n is O(log10n)
O ( log b n ) a bloganO(logbn)ab

Un autre fait intéressant avec les fonctions logarithmiques est que, alors que pour une constante , n'est PAS , mais est depuis qui diffère de par le seul facteur constant .n k O ( n ) log n k O ( log n ) log n k = k log n log n kk>1nkO(n)lognkO(logn)lognk=klognlognk

fade2black
la source
Pas seulement pour les entiers positifs: Pour tout réel , par exemple . ea,b>1e
nbubis
2
J'ajouterais que c'est la raison pour laquelle, avec la notation big-O, la base du logarithme n'est généralement pas spécifiée. Cela signifie également qu'il n'y a pas de confusion quant à la base utilisée: il peut s'agir de l'une des bases couramment utilisées, car elle ne fait aucune différence. O(logn)
svick
9

En plus de la réponse de fade2black (qui est tout à fait correcte), il convient de noter que la notation " " est ambiguë. La base n'est pas 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 (sauf indication contraire), alors que dans certains contextes d’ingénierie, elle peut être égale à 10. En informatique, la base 2 est si omniprésente que est souvent supposé être la base 2. Cela wikipedia L'article ne dit jamais rien de la base.e loglog(n)elog

Mais, comme cela a déjà été démontré, dans ce cas, cela ne compte pas.

MattPutnam
la source
7
Il est probablement intéressant de noter ensuite que, bien que "log (n)" puisse être ambigu, "O (log (n))" n’est pas parce que ce dernier n’a qu’une signification, quelle que soit la base à laquelle vous songez.
Chris