Algoritmos

Logaritmo: quantas rodadas tem um mata-mata de 16 times?

Capa do artigo Logaritmo: quantas rodadas tem um mata-mata de 16 times?
Leitura com foco

Entenda o contexto.
Leve para a prática.

Neste artigo
  1. Como o logaritmo se relaciona com a potência?
  2. Como calcular o logaritmo contando divisões?
  3. Por que o logaritmo aparece nos algoritmos?
  4. Aí você pergunta: e o tal n × log n da ordenação?
  5. Qual é a base: 2, 10 ou e?
  6. Quais são os erros mais comuns com logaritmo?
  7. Agora é com você!

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.

Diagrama de um mata-mata com 16 times que cai para 8, 4, 2 e 1 em quatro rodadas, mostrando que o logaritmo de 16 na base 2 é 4
O logaritmo na base 2 conta quantas vezes dá para dividir por 2 até chegar a 1.

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.

História em quadrinhos em três quadros: uma folha dobrada tem 8 camadas; desfazendo as dobras ela passa a 4, 2 e 1, e as três divisões por 2 são o logaritmo de 8 na base 2
A folha de 8 camadas: três divisões por 2 até chegar a 1. O logaritmo de 8 na base 2 é 3.

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ênciaLogaritmoComo se lê
23 = 8log2 8 = 3O logaritmo de 8 na base 2 é 3
24 = 16log2 16 = 4O logaritmo de 16 na base 2 é 4
210 = 1.024log2 1.024 = 10O logaritmo de 1.024 na base 2 é 10
103 = 1.000log10 1.000 = 3O logaritmo de 1.000 na base 10 é 3
A mesma informação escrita como potência e como logaritmo.

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 vetorOlhando item por item (pior caso)Busca binária (pior caso)
1010 passos4 passos
1.0001.000 passos10 passos
1.000.0001.000.000 de passos20 passos
1.000.000.0001.000.000.000 de passos30 passos
Passos no pior caso: a busca binária cresce com o logaritmo do tamanho.
Gráfico comparando os passos de olhar um por um, que chegam a 64, com os de dividir pela metade, que chegam a 6, em um vetor de 64 valores
Enquanto uma linha sobe junto com o tamanho, a outra quase não sai do chão.

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:

nn × log2 nn × n
82464
1.02410.2401.048.576
1.000.000cerca de 20 milhões1 trilhão
Por que n × log n é tão melhor que n × n.

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 log com 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 com ValueError: 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.

Compartilhe este artigo

Sobre quem escreve

Walmir Silva

Olá! Sou Walmir, engenheiro de software com MBA em Engenharia de Software e o cérebro por trás do GrowthCode e autor do livro "Além do Código".

Se você acha que programação é apenas sobre escrever código, prepare-se para expandir seus horizontes. Aqui, nós vamos além do código e exploramos as interseções fascinantes entre tecnologia, negócios, artes e filosofia.

Você está em busca de crescimento na carreira? Quer se destacar em um mercado competitivo? Almeja uma vida mais rica em conhecimento e realização? Então você chegou ao lugar certo. No GrowthCode, oferecemos insights profundos, estratégias comprovadas e um toque de sabedoria filosófica para catalisar seu crescimento pessoal e profissional.

Ver todos os artigos →

Continue a conversa

Compartilhe sua perspectiva

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Guardamos o IP e o navegador de quem comenta por 6 meses, para barrar spam e porque o Marco Civil da Internet pede a guarda dos registros de acesso por esse prazo. Veja como tratamos seus dados.

Encontre sua próxima resposta

O que você quer aprender?

Preferências de cookies

Os cookies opcionais começam desligados. Você pode mudar a escolha a qualquer momento por esta tela.

NecessáriosSempre ativos

Guardam a sua escolha de cookies e o código do registro dela, e mantêm o site funcionando. Não são usados para publicidade.

Contam visitas e mostram como o site é usado: Google Analytics e Microsoft Clarity, carregados pelo Google Tag Manager.

Exibem anúncios do Google AdSense sem personalização. Os cookies desta categoria limitam a repetição dos anúncios e medem o resultado deles.

Usa a sua navegação para escolher anúncios e formar públicos de anúncio: anúncios do Google escolhidos pelos seus interesses e os indicadores do Google no Analytics. Desligado, os anúncios aparecem sem personalização. Depende de Publicidade.

Também é possível bloquear cookies nas configurações do navegador. Detalhes na Política de privacidade.