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.
Nenhum comentário:
Postar um comentário