Sou novo no entendimento de algoritmos de ciência da computação. Eu entendo o processo da busca binária, mas estou tendo um pequeno mal-entendido quanto à sua eficiência.
Em um tamanho de $ s = 2 ^ n $ elementos, levaria, em média, $ n $ etapas para encontrar um elemento específico. Tomando o logaritmo de base 2 de ambos os lados, obtém-se $ \ log_2 (s) = n $. Então, o número médio de etapas para o algoritmo de pesquisa binária não seria $ \ log_2 (s) $?
Este artigo da Wikipedia em o algoritmo de pesquisa binária diz que o desempenho médio é $ O (\ log n) $. Por que isso acontece? Por que esse número não é $ \ log_2 (n) $?
Comentários
- Duplicar em SO – O log de Big O (logn) é base e?
Resposta
Quando você altera a base do logaritmo, a expressão resultante difere apenas por um fator constante que, por definição de notação Big-O , implica que ambas as funções pertencem à mesma classe com relação ao seu comportamento assintótico.
Por exemplo $$ \ log_ {10} n = \ frac {\ log_ {2} n} {\ log_ {2} 10} = C \ log_ {2} {n} $$ onde $ C = \ frac {1} {\ log_ {2} 10} $.
Então $ \ log_ {10} n $ e $ \ log_ {2} n $ difere por uma constante $ C $ e, portanto, ambos são verdadeiros: $$ \ log_ {10} n \ text {is} O (\ log_ {2} n) $$ $$ \ log_ {2} n \ text {é} O (\ log_ {10} n) $$ Em geral $ \ log_ {a} {n} $ é $ O (\ log_ {b} {n}) $ para inteiros positivos $ a $ e $ b $ maiores que 1.
Outro fato interessante com funções logarítmicas é que enquanto para $ k > 1 $, $ n ^ k $ constante, $ n ^ k $ NÃO é $ O (n) $, mas $ \ log {n ^ k} $ é $ O (\ log {n}) $ já que $ \ log {n ^ k} = k \ log {n} $ que difere de $ \ log {n} $ apenas pelo fator constante $ k $.
Comentários
- Não apenas para inteiros positivos: para todos os reais $ a, b > 1 $, por exemplo $ e $.
- Eu acrescentaria que essa é a razão pela qual, com a notação big-O, a base do logaritmo geralmente não é especificada. Também significa que não há confusão sobre qual base $ O (\ log n) $ usa: pode ser qualquer uma das bases comumente usadas, uma vez que ' não faz diferença.
Resposta
Além da resposta de fade2black “(que está completamente correta), é importante notar que a notação “$ \ log (n) $” é ambígua. A base não é realmente especificada, e a base padrão muda com base no contexto. Em matemática pura, a base quase sempre é considerada $ e $ (a menos que especificado), enquanto em certos contextos de engenharia pode ser 10. Em ciência da computação , a base 2 é tão onipresente que $ \ log $ é freqüentemente considerado como a base 2. Esse artigo da wikipedia nunca diz nada sobre a base.
Mas, como já foi mostrado, neste caso não ” acabam importando.
Comentários
- É provavelmente importante notar então que enquanto " registrar (n) " pode ser ambíguo que " O (log (n)) " não é porque o último só tem um significado, não importa em que base você esteja pensando.