Por que o log no big-O da pesquisa binária não é base 2?

35

Eu sou novo em entender algoritmos de ciência da computação. Entendo o processo da pesquisa binária, mas estou tendo um pequeno mal-entendido com sua eficiência.

Em um tamanho de elementos, seriam necessários, em média, etapas para encontrar um elemento específico. Tomando o logaritmo da base 2 de ambos os lados, produz . Portanto, o número médio de etapas do algoritmo de pesquisa binária não seria ? n log 2 ( s ) = n log 2 ( s )s=2nnlog2(s)=nlog2(s)

Este artigo da Wikipedia sobre o algoritmo de busca binária diz que o desempenho médio é . Porque isto é assim? Por que esse número não é ?log 2 ( n )O(logn)log2(n)

DrPepper
fonte
2
Duplicar no SO - A base de log Big O (logn) e?
Dukeling 19/07/19

Respostas:

86

Quando você altera a base do logaritmo, a expressão resultante difere apenas por um fator constante que, por definição da notação Big-O , implica que ambas as funções pertencem à mesma classe em relação ao seu comportamento assintótico.

Por exemplo que .C=1

log10n=log2nlog210=Clog2n
C=1log210

Então e difere por uma constante , e, portanto, ambos são verdadeiras: de um modo geral é para inteiros positivos e maior do que 1.log 2 n C log 10 n  é  O ( log 2 n ) log 2 n  é  O ( log 10 n ) log a n O ( log b n ) a blog10nlog2nC

log10n is O(log2n)
log2n is O(log10n)
loganO(logbn)ab

Outro fato interessante com funções logarítmicas é que, enquanto a constante , NÃO é , mas é desde que que difere de apenas pelo fator constante .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
fonte
Não apenas para números inteiros positivos: para todos os reais , por exemplo, e . a,b>1e
Nbubis 20/07
2
Eu acrescentaria que essa é a razão pela qual, com a notação big-O, a base do logaritmo geralmente não é especificada. Isso também significa que não há confusão sobre qual base usa: pode ser uma das mais usadas com base, pois não faz diferença. O(logn)
svick
9

log(n)elog

Mas, como já foi demonstrado, neste caso, não acaba importando.

MattPutnam
fonte
7
Provavelmente vale a pena notar ainda que, embora "log (n)" possa ser ambíguo, o fato de "O (log (n))" não ocorrer porque o último tem apenas um significado, não importa em que base você esteja pensando.
Chris