Neste artigo
Logaritmo é o expoente a que uma base precisa ser elevada para chegar a um número. O logaritmo de 8 na base 2 é 3, porque 2 elevado a 3 dá 8. Dito de outro jeito, ele responde a uma pergunta: quantas vezes preciso multiplicar a base por ela mesma para chegar lá?
No artigo sobre busca binária, você jogou o jogo de adivinhar um número de 1 a 100 chutando sempre o meio. Ficou uma pergunta no ar: quantos palpites, no máximo, esse jogo exige? Sete. E para um número de 1 a 1 milhão? Vinte. Essa conta tem nome, logaritmo, e ela aparece de novo em vários algoritmos desta jornada, como o merge sort, o quick sort e o heapsort. Se a palavra lembra uma aula difícil do ensino médio, respire: aqui só vamos precisar de uma ideia, e ela cabe em uma tabela de campeonato. E, se a potência ainda não está firme, passe antes pelo artigo sobre potenciação e crescimento exponencial: o logaritmo é a mesma conta, feita de trás para frente.
Pense em um torneio de mata-mata com 16 times. Na primeira rodada sobram 8. Na segunda, 4. Na terceira, 2. Na quarta sai o campeão. Foram 4 rodadas para 16 times. Se o torneio dobrar de tamanho, para 32 times, quantas rodadas a mais? Uma só! O número de rodadas é o logaritmo do número de times, na base 2.

Como o logaritmo se relaciona com a potência?
O logaritmo é a potência lida de trás para frente. Lembra da folha de papel do artigo sobre potenciação? Lá, você sabia o número de dobras e queria as camadas. Aqui é o contrário: a folha já está dobrada, e a pergunta é quantas dobras foram.

Na potência, você sabe o expoente e quer o resultado. No logaritmo, você sabe o resultado e quer o expoente. É a tabela das potências de 2, lida da direita para a esquerda:
| Potência | Logaritmo | Como se lê |
|---|---|---|
| 23 = 8 | log2 8 = 3 | O logaritmo de 8 na base 2 é 3 |
| 24 = 16 | log2 16 = 4 | O logaritmo de 16 na base 2 é 4 |
| 210 = 1.024 | log2 1.024 = 10 | O logaritmo de 1.024 na base 2 é 10 |
| 103 = 1.000 | log10 1.000 = 3 | O logaritmo de 1.000 na base 10 é 3 |
Em Python, o módulo math faz a conta:
import math print(math.log2(8)) print(math.log2(1024)) print(math.log10(1000)) print(math.log2(1000))
Saída:
3.0 10.0 3.0 9.965784284662087
As três primeiras respostas são exatas, porque 8, 1.024 e 1.000 são potências redondas da base. A última não é: 1.000 fica entre 29, que vale 512, e 210, que vale 1.024. Por isso o logaritmo ficou entre 9 e 10.
Como calcular o logaritmo contando divisões?
Existe um jeito de enxergar o logaritmo na base 2 sem fórmula nenhuma: conte quantas vezes dá para dividir o número por 2 até chegar a 1. É o torneio de mata-mata, rodada por rodada. Veja em Python:
def contar_divisoes(numero):
divisoes = 0
while numero > 1:
numero = numero // 2
divisoes += 1
return divisoes
for numero in [8, 1000, 1024, 1000000]:
print(numero, contar_divisoes(numero))
Saída:
8 3 1000 9 1024 10 1000000 19
Para 8 e 1.024, a contagem bate com o math.log2. Para 1.000, deu 9, e o valor exato era 9,97. A contagem com divisão inteira entrega o logaritmo arredondado para baixo, que os livros chamam de piso. Um material de algoritmos da UFSCar usa exatamente essa leitura: o maior número de vezes que o valor pode ser dividido por 2.
Em PHP:
<?php
function contarDivisoes(int $numero): int
{
$divisoes = 0;
while ($numero > 1) {
$numero = intdiv($numero, 2);
$divisoes++;
}
return $divisoes;
}
foreach ([8, 1000, 1024, 1000000] as $numero) {
echo $numero, " ", contarDivisoes($numero), "\n";
}
Em C:
#include <stdio.h>
int contar_divisoes(int numero)
{
int divisoes = 0;
while (numero > 1) {
numero = numero / 2;
divisoes++;
}
return divisoes;
}
int main(void)
{
int numeros[] = {8, 1000, 1024, 1000000};
for (int i = 0; i < 4; i++) {
printf("%d %d\n", numeros[i], contar_divisoes(numeros[i]));
}
return 0;
}
As duas versões mostram a mesma saída do Python. Foque no conceito, e não na linguagem!
Por que o logaritmo aparece nos algoritmos?
Porque todo algoritmo que descarta metade do problema a cada passo termina em um número de passos ligado ao logaritmo do tamanho. A busca binária é o exemplo mais direto. Este programa conta os passos dela no pior caso, quando o valor procurado não está no vetor:
def passos_da_busca_binaria(tamanho):
# pior caso: o valor procurado é maior que todos os do vetor
inicio = 0
fim = tamanho - 1
passos = 0
while inicio <= fim:
meio = (inicio + fim) // 2
passos += 1
inicio = meio + 1
return passos
for tamanho in [10, 1000, 1000000, 1000000000]:
print(tamanho, passos_da_busca_binaria(tamanho))
Saída:
10 4 1000 10 1000000 20 1000000000 30
| Tamanho do vetor | Olhando item por item (pior caso) | Busca binária (pior caso) |
|---|---|---|
| 10 | 10 passos | 4 passos |
| 1.000 | 1.000 passos | 10 passos |
| 1.000.000 | 1.000.000 de passos | 20 passos |
| 1.000.000.000 | 1.000.000.000 de passos | 30 passos |

O vetor ficou mil vezes maior, e a busca binária pediu só 10 passos a mais. Sacou a força disso? A regra geral, demonstrada em um material de aula do IME-USP, é que a busca binária nunca passa de log2 n + 1 passos.
Aí você pergunta: e o tal n × log n da ordenação?
É a mesma ideia, usada várias vezes. Um algoritmo como o merge sort divide o vetor ao meio, depois divide cada metade ao meio, e assim por diante. O número de níveis dessa divisão é log2 n. Em cada nível, todos os n valores são percorridos uma vez. O trabalho total fica n × log2 n:
| n | n × log2 n | n × n |
|---|---|---|
| 8 | 24 | 64 |
| 1.024 | 10.240 | 1.048.576 |
| 1.000.000 | cerca de 20 milhões | 1 trilhão |
Para um milhão de valores, a diferença é de 20 milhões de operações contra 1 trilhão. É por isso que os próximos artigos de ordenação insistem tanto em dividir o problema ao meio.
Qual é a base: 2, 10 ou e?
A base muda conforme a pergunta. Na computação, quase sempre é 2, porque os algoritmos dividem por 2. A base 10 conta ordens de grandeza: o logaritmo de 1.000 na base 10 é 3, o número de zeros. E existe uma terceira base, o número e, que vale cerca de 2,718 e aparece em fórmulas de matemática e de estatística. O logaritmo nessa base é chamado de logaritmo natural.
ATENÇÃO: em Python, math.log com um argumento só calcula o logaritmo natural, e não o de base 10 nem o de base 2:
import math print(math.log(100)) print(math.log10(100)) print(math.log(1000, 10)) print(math.log10(1000))
Saída:
4.605170185988092 2.0 2.9999999999999996 3.0
Repare na terceira linha. Pedir a base 10 como segundo argumento deu 2,9999999999999996 no lugar de 3. A documentação do Python explica que, com dois argumentos, a conta é feita pela divisão de dois logaritmos, e aponta math.log10 e math.log2 como as formas que costumam ser mais precisas.
Quais são os erros mais comuns com logaritmo?
- Confundir logaritmo com divisão. O logaritmo de 16 na base 2 não é 16 ÷ 2. É o número de vezes que dá para dividir por 2 até chegar a 1: quatro.
- Esquecer a base. O logaritmo de 1.000 é 3 na base 10 e quase 10 na base 2. Sem a base, a pergunta está incompleta.
- Usar a função log achando que é base 10. Em Python, PHP e C, a função
logcom um argumento calcula o logaritmo natural: para 100, as três devolvem 4,605. - Pedir o logaritmo de zero ou de número negativo. Não existe expoente que leve o 2 até o zero. Em Python,
math.log2(0)para o programa comValueError: math domain error.
Agora é com você!
Primeiro no papel, sem calculadora. Quanto é o logaritmo de 64 na base 2? Quantas rodadas tem um mata-mata com 128 times? E quantos passos, no pior caso, a busca binária leva em um vetor com 2.000 valores? Escreva as três respostas e só depois confira com os programas do artigo.
Depois, no computador: adapte a função que conta divisões para receber também a base. Com base 3, ela deve contar quantas vezes dá para dividir por 3. Teste com 81 e com 100. Tente sozinho, sem pedir a resposta pronta para ninguém, nem para a IA!
No próximo artigo desta série de base, trocamos de trilha: os tipos de variáveis na estatística, o primeiro passo antes de qualquer conta com dados. Até lá!
Confiança Sempre!!!
Fontes:
- Universidade Federal de São Carlos, disciplina Algoritmos e Estruturas de Dados 1, professor Mário César San Felice. Aula 1, com a definição de logaritmo na base 2 e o cálculo do piso por divisões sucessivas.
- Instituto de Matemática e Estatística da USP, material de aula. Busca binária: número de iterações, com a demonstração do limite de passos da busca binária.
- Python Software Foundation, documentação oficial. math: Mathematical functions, com as funções log, log2 e log10.
- Universidade Federal de Pernambuco, material de aula. Análise de Complexidade de Algoritmos, com o lg n entre as funções usadas como referência.
- Universidade Federal do Ceará, notas de aula. Recorrências, aula 2, com a prova de que a busca binária recursiva cresce como o logaritmo de n.
- Slides de Estrutura de Dados (2007). Aula 4: algoritmos de busca, com o número máximo de iterações da busca binária, 1 + log2 n.
- Universidade de São Paulo, repositório. Análise de Algoritmos, com um algoritmo recursivo para o piso do logaritmo na base 2.
- Instituto de Matemática e Estatística da USP, lista de exercícios. MAC5711 Análise de Algoritmos, lista 1, com a convenção de que lg n é o logaritmo na base 2.
- Universidade Federal de São Carlos, disciplina Projeto e Análise de Algoritmos. Análise assintótica, com exemplos de funções da ordem de n lg n.
- Os exemplos deste artigo foram executados em Python 3.13, PHP 8.3 e GCC 13.

Continue a conversa