Qual é o valor da base dos logaritmos nas notações assintóticas?

Por
| 

Ao representar a complexidade de um algoritmo, é comum nos depararmos com logaritmos nas notações assintóticas.

Por exemplo, a complexidade da pesquisa binária é O(logn). Mas qual é o valor da base desse logaritmo?

O fato é que a notação assintótica torna o valor da base irrelevante. Isso é uma consequência da propriedade da mudança de base dos logaritmos, já que logaritmos de um mesmo número em diferentes bases diferem apenas por uma constante multiplicativa [1].

No caso da busca binária, vamos supor que a base seja 10: O(log10n). Agora, vamos mudar a base para 2:

O(log10n)=O(log2nlog210)=O(log2n×1log210)=O(log2n)

Na última etapa, a constante 1log210 foi absorvida pela notação Big-O (o mesmo ocorreria se fosse a notação Θ ou Ω). Também concluímos que O(log10n)=O(log2n). Esse resultado pode ser estendido para outras bases e complexidades de outros algoritmos.

Respondendo a pergunta do título: se considerarmos as definições das notações assintóticas (Big-O, Θ, Ω), então qualquer valor real que satisfaça a definição dos logaritmos pode servir de base.

Por fim, essa "liberdade" para escolher a base é vantajosa, por exemplo, para resolver recorrências com o método de Akra-Bazzi, pois se a função de custo possuir um logaritmo, então podemos escolher uma base que seja conveniente para realizar a integração, como a constante de Neper.

Leia também: Teorema Mestre e Exemplos Resolvidos

Referências

[1] SODRÉ, U. (2006). ENSINO MÉDIO :: Logaritmos. Acesso em 5 de abril de 2018.

Sugestões de livros para estudantes de computação na Amazon (patrocinado): Lista de Livros

Obrigado pela leitura! Se você puder, considere apoiar financeiramente o Blog Cyberini, Chave Pix: cyberpix9@gmail.com

Doar com PayPal

Siga o blog

Redes sociais: Facebook, Twitter, YouTube, Pinterest, Instagram, Telegram

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário

Este site usa cookies para fornecer serviços, analisar o tráfego e exibir publicidade personalizada, conforme a nossa política de privacidade. Seus dados, como IP e user agent, são compartilhados com nossos parceiros (como o Google). Saiba Mais

RecusarAceitar