Notação Big O Explicada com Exemplos de Código

Uma busca em um dicionário Python leva cerca de 100 nanossegundos, não importa se o dicionário tem 1.000 ou 1.000.000 de chaves. Um laço duplo que procura duplicatas em uma lista leva meio milissegundo com 200 itens e 136 milissegundos com 3.200. Dezesseis vezes a entrada, quase 280 vezes a espera. Mesma máquina, mesmo Python. A notação Big O é o nome dessa diferença.

O que a notação Big O mede

Big O descreve como o tempo de execução (ou o uso de memória) de um trecho de código cresce conforme a entrada aumenta. Não é uma leitura de cronômetro, e não importa se o seu notebook é rápido ou lento. O que importa é a forma da curva de crescimento: ao dobrar a entrada, o tempo dobra, quadruplica ou quase não muda?

A notação descarta tudo o que não muda essa forma, de fatores constantes ao hardware em que o código roda. O(n) significa “proporcional a n”, seja o custo real 3n + 7 ou 0.001n + 1000000. Torne n grande o suficiente e só resta a forma.

Exemplos de Big O em Python, cronometrados com entradas crescentes

Cada função abaixo foi cronometrada com o módulo timeit do Python na versão 3.11, em tamanhos de entrada separados por uma ordem de grandeza (ou o dobro).

Tempo constante: uma busca em dicionário

1
2

def dict_lookup(d, key):
    return d[key]

A entrada cresce mil vezes. O tempo por chamada permanece estável, dentro do ruído de medição. Um dicionário é uma tabela hash: o Python calcula o hash da chave e pula direto para o bucket correspondente, não importa quantas outras entradas existam. Isso é O(1), tempo constante.

Tempo linear: somar uma lista

1
2
3
4
5

def sum_loop(nums):
    total = 0
    for n in nums:
        total += n
    return total

Cada aumento de dez vezes em n traz um aumento de tempo de aproximadamente dez vezes. O laço toca cada elemento exatamente uma vez, então o trabalho escala diretamente com a entrada. Isso é O(n), tempo linear, e é onde vive a maior parte do código do dia a dia.

Tempo quadrático: buscar duplicatas da forma ingênua

1
2
3
4
5
6

def has_duplicate_naive(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

Dobrar n aproximadamente quadruplica o tempo a cada passo. O laço externo roda n vezes e o interno roda quase n vezes a cada iteração externa, então o trabalho total é proporcional a n * n. Isso é O(n^2), tempo quadrático. É a classe que arruína o código em produção, porque parece inofensiva em um teste com 50 linhas e estoura o tempo limite com 50.000.

Tempo logarítmico: busca binária

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def binary_search(sorted_nums, target):
    lo, hi = 0, len(sorted_nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_nums[mid] == target:
            return mid
        elif sorted_nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Um aumento de mil vezes em n praticamente só dobra o tempo. Cada passo do laço descarta metade do intervalo restante, então o número de passos necessários cresce com log2(n) em vez de com n: cerca de 10 passos para mil itens, cerca de 20 para um milhão. Isso é O(log n). O git bisect executa o mesmo algoritmo sobre o histórico de commits em vez de um array ordenado: encontra o commit que quebrou algo entre centenas de candidatos em poucos passos, porque cada teste descarta metade do intervalo restante.

Tempo linearítmico: ordenar

1

sorted_nums = sorted(nums)

Cada passo de dez vezes em n custa mais do que dez vezes em tempo, mas bem longe das cem vezes que um algoritmo quadrático mostraria. O sorted() do Python usa Timsort, que faz O(n log n) comparações: a mesclagem acontece em cerca de log n rodadas, e cada rodada toca cada um dos n elementos uma vez para unir sequências adjacentes. Toda ordenação de propósito geral que você vai usar no dia a dia (Timsort, mergesort, o caso médio do quicksort) cai aqui, por isso O(n log n) é tratado como “o melhor que uma ordenação pode entregar” em vez de comparado com O(n).

As classes de complexidade Big O mais comuns, da mais rápida à mais lenta

Observe as duas últimas linhas. Ir de O(n log n) para O(n^2) com um milhão de itens é a diferença entre um relatório que roda em um segundo e um que ainda está rodando quando alguém mata o processo.

O que a notação Big O não diz

Big O descreve o crescimento assintótico, ou seja, o que acontece quando n fica arbitrariamente grande. Três coisas escapam por essa lacuna.

Constantes são invisíveis. Um O(n) com fator constante de 1000 pode ser mais lento na prática do que um O(n^2) com uma constante minúscula, para qualquer n que você algum dia vá ver. Big O diz qual curva vence no final, não qual função é mais rápida com os seus dados. É por isso que o insertion sort, que é O(n^2), continua sendo a melhor opção para arrays bem pequenos, e por isso o Timsort usa um insertion sort binário para construir cada pequena sequência (run) até um comprimento mínimo (minrun, tipicamente 32-64 elementos) antes de começar a mesclar as sequências entre si.

Um n pequeno não mostra a curva. Os tempos quadráticos acima só ficaram visivelmente quadráticos quando n passou de algumas centenas. Com n = 10, quase tudo termina antes que você perceba, por isso uma função pode passar em todos os testes que você escreve localmente e ainda assim falhar nos volumes de dados de produção.

A complexidade de espaço é um eixo separado. dict_lookup, sum_loop, has_duplicate_naive e binary_search rodam todas com memória extra praticamente constante: nenhuma aloca uma segunda estrutura de dados proporcional à entrada. sorted() aloca sim: devolve uma lista nova do mesmo tamanho da entrada, O(n) de espaço, porque nunca ordena no lugar. Alguns algoritmos trocam memória por velocidade de propósito: uma função de Fibonacci com memoização guarda cada resultado já calculado, gastando O(n) de espaço para transformar O(2^n) de tempo em O(n). Ao declarar a complexidade de uma função, diga qual eixo você quer dizer: a versão mais rápida costuma ser a que usa mais memória.

Como identificar um O(n^2) escondido no seu código

O laço duplo de antes é o caso óbvio. O que chega à produção normalmente não tem nenhum laço aninhado à vista.

Testes de pertencimento dentro de um laço. x in alguma_lista é O(n) em uma lista, porque o Python precisa percorrê-la inteira. Rodar esse teste dentro de um laço que já roda n vezes dá O(n^2) sem nenhum segundo for à vista:

1
2
3
4
5
6

# O(n^2): "in" percorre a lista inteira a cada iteração
seen = []
for item in items:
    if item in seen:
        continue
    seen.append(item)

Troque a lista por um set, onde o pertencimento é O(1), e o laço cai para O(n):

1
2
3
4
5
6

# O(n): "in" é uma busca por hash
seen = set()
for item in items:
    if item in seen:
        continue
    seen.add(item)

Reconstruir uma lista em vez de adicionar itens a ela. result + [item] aloca uma lista nova e copia cada elemento já existente para dentro dela; result.append(item) faz a lista existente crescer no lugar.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def build_with_plus(n):
    result = []
    for i in range(n):
        result = result + [i]   # copia tudo que já foi construído, toda vez
    return result

def build_with_append(n):
    result = []
    for i in range(n):
        result.append(i)        # O(1) amortizado
    return result

Construir uma lista de 8.000 itens com + levou 65 ms. A mesma lista com .append() levou 0,15 ms. A diferença aumenta conforme n cresce, porque um é quadrático e o outro é linear.

A consulta N+1. Você busca uma lista de linhas e depois percorre cada uma delas disparando mais uma consulta por linha para dados relacionados, e uma única consulta virou n + 1: O(n) idas e voltas ao banco de dados em vez de uma só. Um índice, como visto em como funcionam os índices de banco de dados, transforma uma única busca de uma varredura O(n) da tabela em O(log n). Isso não ajuda em nada um laço que envia mil consultas separadas. A correção tem o mesmo formato da correção do set acima: substitua a operação por linha por uma operação feita uma única vez. Aqui, isso significa uma única consulta com um join, que os tipos de JOIN em SQL explicados com exemplos detalha.

Como medir a complexidade do seu próprio código

Escolha a função suspeita, geralmente uma com um laço cujo número de iterações depende do tamanho dos dados. Cronometre-a com timeit em três ou quatro tamanhos de entrada, cada um dez vezes o anterior, e divida cada tempo pelo anterior. Uma razão próxima de 1 é O(1) ou O(log n). Próxima de 10 é linear. Entre 10 e 100 é O(n log n), como a faixa de 17 a 21 que a tabela do sorted() mostra. Próxima de 100 significa que há um O(n^2) para caçar; se isso tornar os tamanhos grandes lentos demais para esperar, dobre n em vez de multiplicar por dez e procure uma razão próxima de 4. Comece pelos testes de pertencimento em listas e pelas reconstruções com + dentro desse laço, depois qualquer consulta enviada uma vez por linha.

Artigos relacionados

• Git Bisect: Como Encontrar o Commit que Quebrou seu Código
• Como Funcionam os Índices de Banco de Dados
• Tipos de JOIN em SQL Explicados com Exemplos