Preciso saber calcular complexidade formalmente?

Não para o dia a dia. Basta reconhecer padrões: um laço sobre a coleção é O(n), um laço dentro de outro sobre a mesma coleção é O(n ao quadrado), e buscar em set ou dict é O(1). Esse reconhecimento já orienta as maiores decisões de performance sem nenhuma conta.

Sempre devo trocar lista por set?

Não. O set brilha para verificar pertencimento e para eliminar duplicados, mas ele não guarda ordem nem permite índice. Se você depende da ordem, de itens repetidos ou de acessar pela posição, a lista continua sendo a escolha certa. A regra é decidir pela operação mais frequente.

A busca por chave em dict também é O(1)?

Sim. O dict usa a mesma tabela de dispersão do set, então acessar um valor pela chave é praticamente instantâneo, independente do tamanho do dicionário. É por isso que o dict é a estrutura ideal quando você associa chaves a valores e consulta muito.

O que é um laço aninhado e por que é um alerta?

É um laço dentro de outro percorrendo a mesma coleção. Isso faz o número de operações crescer com o quadrado do tamanho, ou seja, O(n ao quadrado). Em entradas grandes o tempo explode. Muitas vezes dá para eliminar o laço interno usando um set ou dict para a busca.

Reduzir complexidade sempre vale mais que microtrucos?

Na esmagadora maioria dos casos com entradas grandes, sim. Trocar O(n) por O(1) muda a ordem de grandeza do tempo, algo que nenhum ajuste fino de linha alcança. Só depois de acertar a estrutura e o algoritmo é que microtrucos, medidos com timeit, fazem diferença perceptível.

Módulo 14 - Performance e profiling

Complexidade e a estrutura de dados certa

10 min de leitura · por Cesar Gargiulo, revisado pela equipe ValorFinal e GuardiaSec · Atualizado em 01/07/2026

O que você vai aprender

Entender a notação O(n) sem matemática pesada.
Comparar o custo de buscar em lista, set e dict.
Reconhecer o padrão do laço aninhado como sinal de alerta.
Escolher a estrutura de dados pela operação mais frequente.

Complexidade sem matemática pesada

Complexidade assusta pelo nome, mas a ideia é simples: como o tempo cresce quando a entrada cresce. Se uma operação leva o mesmo tempo com 10 ou com 10 milhões de itens, ela é O(1), tempo constante. Se o tempo dobra quando os itens dobram, ela é O(n), linear. Se o tempo quadruplica quando os itens dobram, ela é O(n ao quadrado), quadrática, e isso vira um problema sério em entradas grandes. Você não precisa calcular nada; precisa reconhecer o padrão. Um laço que percorre a lista é O(n). Um laço dentro de outro laço sobre a mesma lista é O(n ao quadrado), o clássico sinal de alerta.

Por que isso importa mais que qualquer microtruque? Porque a diferença entre O(n) e O(1) é de outra ordem de grandeza. Numa lista de um milhão de itens, uma busca O(n) pode olhar um milhão de elementos; uma busca O(1) olha quase nenhum. Nenhum truque de sintaxe compensa uma diferença dessas. Por isso a otimização mais poderosa quase sempre é estrutural: trocar a estrutura de dados ou o algoritmo para reduzir a complexidade, e não afinar linha por linha.

Complexidade	Como o tempo cresce	Exemplo típico
O(1)	Não muda com o tamanho	Buscar em dict, acessar lista por índice
O(n)	Em linha reta com o tamanho	Percorrer uma lista, buscar valor em lista
O(n log n)	Um pouco mais que linear	Ordenar com sorted
O(n ao quadrado)	Explode com o tamanho	Laço dentro de laço sobre a mesma lista

As complexidades mais comuns no dia a dia e onde você as encontra.

Buscar em lista contra buscar em set

O caso mais comum e mais caro de estrutura errada é usar uma lista para perguntar contém este valor. Verificar se um item está numa lista faz o Python varrer a lista do começo até achar, ou até o fim se não achar: é O(n). Já um set ou as chaves de um dict usam uma tabela de dispersão, que calcula onde o valor deveria estar e vai quase direto: é O(1). Para uma verificação feita muitas vezes, essa troca sozinha transforma um programa lento em instantâneo.

import timeit

lista = list(range(100000))
conjunto = set(lista)

# Procurar um valor que esta no fim: pior caso da lista
t_lista = timeit.timeit("99999 in lista", globals=globals(), number=1000)
t_set = timeit.timeit("99999 in conjunto", globals=globals(), number=1000)

print(f"99999 in lista: {t_lista:.4f}s")
print(f"99999 in set:   {t_set:.4f}s")
# O set costuma ser centenas de vezes mais rapido

in lista é O(n) e varre tudo; in set é O(1) e vai quase direto. A diferença é enorme.

Lista para pertencimento (O(n))

Varre do início até achar o item
Fica mais lenta conforme a lista cresce
Ótima para ordem e itens repetidos
Ruim para perguntar contém este valor

Set ou dict para pertencimento (O(1))

Vai quase direto ao lugar do item
Tempo praticamente constante
Set ignora ordem e não repete
Ideal para verificação de pertencimento

Escolher a estrutura pela operação frequente

A regra prática para não errar é escolher a estrutura pela operação que você faz com mais frequência. Se o programa vive perguntando este valor existe, use um set. Se ele associa uma chave a um valor e consulta muito, use um dict, cuja busca por chave também é O(1). Se a ordem importa e você percorre do começo ao fim, a lista é certa. Se você adiciona e remove nas duas pontas o tempo todo, existe uma estrutura melhor, a deque, tema da próxima aula. Não há estrutura melhor no vácuo; há a melhor para o que você faz mais vezes.

clientes = ["ana@x.com", "bruno@x.com", "carla@x.com"]  # muitos milhares

# Ruim: para cada pedido, procura o email na lista (O(n) por consulta)
cadastrados = clientes

# Bom: converte uma vez para set; cada consulta vira O(1)
cadastrados = set(clientes)

if "carla@x.com" in cadastrados:
    print("cliente cadastrado")

Se você vai consultar pertencimento muitas vezes, converta a lista para set uma vez só.

Teste rápido

Por que buscar um valor com in é muito mais rápido em set do que em lista?

Perguntas frequentes

Preciso saber calcular complexidade formalmente?: Não para o dia a dia. Basta reconhecer padrões: um laço sobre a coleção é O(n), um laço dentro de outro sobre a mesma coleção é O(n ao quadrado), e buscar em set ou dict é O(1). Esse reconhecimento já orienta as maiores decisões de performance sem nenhuma conta.
Sempre devo trocar lista por set?: Não. O set brilha para verificar pertencimento e para eliminar duplicados, mas ele não guarda ordem nem permite índice. Se você depende da ordem, de itens repetidos ou de acessar pela posição, a lista continua sendo a escolha certa. A regra é decidir pela operação mais frequente.
A busca por chave em dict também é O(1)?: Sim. O dict usa a mesma tabela de dispersão do set, então acessar um valor pela chave é praticamente instantâneo, independente do tamanho do dicionário. É por isso que o dict é a estrutura ideal quando você associa chaves a valores e consulta muito.
O que é um laço aninhado e por que é um alerta?: É um laço dentro de outro percorrendo a mesma coleção. Isso faz o número de operações crescer com o quadrado do tamanho, ou seja, O(n ao quadrado). Em entradas grandes o tempo explode. Muitas vezes dá para eliminar o laço interno usando um set ou dict para a busca.
Reduzir complexidade sempre vale mais que microtrucos?: Na esmagadora maioria dos casos com entradas grandes, sim. Trocar O(n) por O(1) muda a ordem de grandeza do tempo, algo que nenhum ajuste fino de linha alcança. Só depois de acertar a estrutura e o algoritmo é que microtrucos, medidos com timeit, fazem diferença perceptível.

Fontes

Seu progresso fica salvo neste aparelho. Assinantes sincronizam entre os aparelhos.

← Achar o gargalo com cProfile e pstats Concluir e avançar →