Arrays, mapas e complexidade
Entenda Big O pela intuição, escolha entre lista, set e dicionário e resolva os padrões mais cobrados em entrevistas explicando o custo.
Cerca de 16 min · Revisado em
Ao final, você vai conseguir
- Classificar trechos de código em O(1), O(log n), O(n) e O(n²)
- Escolher set ou dicionário em vez de lista para buscas e explicar a troca entre tempo e espaço
- Resolver deduplicação, contagem de frequência e soma de pares com uma única passada pela lista
- Aplicar dois ponteiros e janela deslizante a problemas de pontas e de trechos seguidos
- Testar soluções com lista vazia, valores repetidos e limites
Uma função que funciona com 10 clientes pode travar o sistema com 1 milhão. Em entrevistas, depois de “funciona?”, a pergunta seguinte quase sempre é “e se a lista tiver um milhão de itens?”. Saber responder isso não exige matemática avançada: exige reconhecer meia dúzia de padrões e escolher a estrutura certa para guardar os dados.
Procurar um nome: lista solta ou agenda
Um algoritmo é a receita de passos que resolve um problema. Chamamos de n o tamanho da entrada: quantos itens tem a lista, quantos clientes tem o cadastro. A pergunta que importa é: quando n dobra, o trabalho dobra, quadruplica ou quase não muda?
A notação Big O (lê-se “ó grande”) responde exatamente isso. O(n) quer dizer “o trabalho cresce na mesma proporção da entrada”. Ela ignora detalhes como a velocidade do computador e olha o pior caso: a entrada que mais faz o código trabalhar.
constante: O(1)
O trabalho não depende do tamanho da entrada.
pegar a posição 3 de uma lista, ou abrir a agenda direto na aba certa.
const notas = [7, 9, 6, 10];
console.log(notas[3]);logarítmica: O(log n)
A cada passo, o problema cai pela metade. Dobrar a entrada acrescenta um passo só.
procurar uma palavra no dicionário de papel abrindo no meio e descartando metade.
let n = 1000000;
while (n > 1) {
n = Math.floor(n / 2);
}linear: O(n)
O trabalho cresce na mesma proporção da entrada.
folhear o caderno de fiado inteiro procurando um nome.
for (const nome of caderno) {
if (nome === "Lúcia") console.log("achei");
}quadrática: O(n²)
Para cada item, o código percorre todos os itens de novo. Dobrar a entrada quadruplica o trabalho.
comparar cada cliente com todos os outros para achar repetidos.
for (const a of clientes) {
for (const b of clientes) {
comparar(a, b);
}
}| Complexidade | n = 10 | n = 1.000 | n = 1.000.000 |
|---|---|---|---|
O(1) | 1 | 1 | 1 |
O(log n) | 3 | 10 | 20 |
O(n) | 10 | 1.000 | 1.000.000 |
O(n²) | 100 | 1.000.000 | 1.000.000.000.000 |
Classifique cada trecho pela forma como o trabalho cresce com o tamanho da lista.
O(1) · O(log n) · O(n) · O(n²)
notas[3]: pegar uma posição da listacpf in cadastrados, sendocadastradosumset- Repetir
n = n // 2aténchegar a 1 - Busca binária: abrir no meio de uma lista ordenada e descartar metade
sum(precos): somar todos os preços"Ana" in nomes, sendonomesuma lista- Um laço dentro de outro comparando todos os pares de clientes
- Para cada pedido, procurar o cliente dele numa lista com
in
Percorrer uma lista de 1.000 nomes leva 1 segundo. Quanto tempo, mais ou menos, leva com 2.000 nomes num código O(n)? E num código O(n²)?
No O(n), cerca de 2 segundos: o dobro da entrada, o dobro do trabalho. No O(n²), cerca de 4 segundos, porque 2 × 2 = 4. Com 10 vezes mais nomes, seriam 10 segundos contra 100. É por isso que O(n²) costuma ser o alvo da pergunta “dá para melhorar?”.
Lista, set e dicionário: onde procurar rápido
- Lista (array)
- Itens em ordem, acessados pela posição:
nomes[0]. Pegar pela posição éO(1), mas perguntar “este valor está aqui?” obriga a olhar um por um:O(n). - Set (conjunto)
- Guarda valores sem repetição e sem posição. Perguntar se um valor está no
setéO(1)em média. Em JavaScript,new Set(). - Dicionário (mapa)
- Guarda pares chave e valor, como CEP e endereço. Buscar pela chave é
O(1)em média. Em JavaScript,new Map()ou um objeto. - Complexidade de espaço
- Quanta memória extra o algoritmo usa. Um
setcom todos os itens vistos custaO(n)de espaço: você troca memória por velocidade.
A mesma pergunta, “este CPF já está cadastrado?”, com lista e com set.
Python
cadastrados_lista = ["111", "222", "333"]
cadastrados_set = set(cadastrados_lista)
"333" in cadastrados_lista # O(n): confere um por um
"333" in cadastrados_set # O(1): vai diretoJavaScript
const cadastradosLista = ["111", "222", "333"];
const cadastradosSet = new Set(cadastradosLista);
cadastradosLista.includes("333"); // O(n)
cadastradosSet.has("333"); // O(1)Qual é a complexidade de tempo desta função, para uma lista com n itens?
def remover_repetidos(itens):
resultado = []
for item in itens:
if item not in resultado:
resultado.append(item)
return resultadoO(n²)O(n), porque só tem umforO(1), porqueappendé instantâneoO(log n), porque a lista resultado é menor que a original
Deduplicar a lista do mutirão
A planilha de inscrições do mutirão tem e-mails repetidos. Escreva remover_repetidos(itens) que mantém a primeira aparição de cada item, na ordem original, guardando o que já viu num set (crie com set()). O atalho list(set(itens)) perde a ordem.
def remover_repetidos(itens):
return list(set(itens))
print(remover_repetidos([3, 1, 3, 2, 1])) # esperado: [3, 1, 2]- Mantém a ordem da primeira aparição
- Lista sem repetidos volta igual
- Funciona com e-mails
- Lista vazia devolve lista vazia
- Usa um set para lembrar o que já viu
Padrão 1: contar com um dicionário
Muitos problemas de entrevista são, no fundo, “quantas vezes cada coisa aparece?”: a palavra mais repetida, o produto mais vendido, se duas palavras são anagramas. O padrão é sempre o mesmo: percorrer a lista uma vez e ir somando num dicionário, como alguém marcando tracinhos ao lado de cada nome na apuração da eleição do grêmio.
Contando votos com um dicionário. Observe a memória mudar a cada volta.
votos = ["frango", "atum", "frango"]
contagem = {}
for voto in votos:
contagem[voto] = contagem.get(voto, 0) + 1
print(contagem)- Linha 1: A lista de votos é criada.
- Linha 2: O dicionário começa vazio: ninguém tem votos ainda.
- Linha 3: Primeira volta:
votorecebe"frango". - Linha 4:
contagem.get("frango", 0)devolve 0, porque a chave ainda não existe. Somando 1, fica 1. - Linha 4: Segunda volta, com
"atum": mesma ideia, nova chave com 1. - Linha 4: Terceira volta: agora
getencontra"frango"com 1 e soma mais 1. Cada voto custou um acessoO(1)ao dicionário. - Linha 5: Uma passada só pela lista:
O(n)de tempo e, no pior caso,O(n)de espaço, se todos os votos forem diferentes. Saída: {'frango': 2, 'atum': 1}
Complete a linha que conta cada item, usando o valor padrão para chaves que ainda não existem.
contagem = {}
for item in itens:
contagem[item] = contagem.____(item, ____) + 1Contagem de frequência em Python e em JavaScript.
Python
contagem = {}
for voto in votos:
contagem[voto] = contagem.get(voto, 0) + 1
# atalho da biblioteca padrão
from collections import Counter
Counter(votos).most_common(1)JavaScript
const contagem = new Map();
for (const voto of votos) {
contagem.set(voto, (contagem.get(voto) || 0) + 1);
}A apuração do sabor de pizza
A turma votou no sabor da pizza da confraternização. Corrija contar(votos) para devolver quantos votos cada sabor teve e mais_votado(votos) para devolver o vencedor. Em empate, vence o que apareceu primeiro; se ninguém votou, devolva None.
def contar(votos):
contagem = {}
for voto in votos:
contagem[voto] = 1
return contagem
def mais_votado(votos):
contagem = contar(votos)
return max(contagem, key=contagem.get)
print(contar(["calabresa", "mussarela", "calabresa"]))- Conta os votos repetidos
- Encontra o sabor mais votado
- Em empate, vence quem apareceu primeiro
- Sem votos, devolve None
- Contar uma lista vazia devolve um dicionário vazio
Padrão 2: lembrar o que já viu
Um clássico de entrevista: dada uma lista de preços e um valor, achar dois produtos que somam exatamente esse valor. Pense num vale-presente de R$ 100 que você quer gastar sem sobrar troco. A solução óbvia testa todos os pares com dois laços: O(n²). Com 100 mil produtos, são cerca de 5 bilhões de comparações.
O truque é inverter a pergunta. Ao olhar um produto de R$ 30, você não precisa testar todos os outros: precisa saber se já passou por um de R$ 70. Guardando cada preço visto num dicionário (preço e posição), essa pergunta custa O(1), e a lista é percorrida uma vez só.
Procurando dois preços que somam 100. Repare que a pergunta vem antes de guardar.
def dois_somam(precos, alvo):
vistos = {}
for i, preco in enumerate(precos):
falta = alvo - preco
if falta in vistos:
return (vistos[falta], i)
vistos[preco] = i
return None
print(dois_somam([30, 50, 70], 100))- Linha 1: O Python guarda a função. Nada roda ainda.
- Linha 10: A chamada: preços 30, 50 e 70, alvo 100.
- Linha 2: O dicionário
vistosvai guardar cada preço já visitado e a posição dele. - Linha 4: Posição 0, preço 30. Para fechar 100, falta 70.
- Linha 7: Nenhum 70 visto ainda. Guardamos o 30 e seguimos.
- Linha 7: Posição 1, preço 50, falta 50. O 50 ainda não está em
vistos(ele mesmo não conta), então é guardado. - Linha 5: Posição 2, preço 70, falta 30. E o 30 está em
vistos, na posição 0. - Linha 10: A função devolve as posições 0 e 2. Três visitas, nenhum laço aninhado:
O(n)de tempo. Saída: (0, 2)
Depois que você explica a versão com dicionário, a pessoa entrevistadora pergunta: “e quanto ela gasta de memória?”. Qual é a melhor resposta?
O(n)de espaço, porque no pior caso o dicionário guarda todos os preços. Troquei memória por tempo: a versão com dois laços usaO(1)de espaço, masO(n²)de tempoO(1), porque o dicionário é rápidoO(n²), porque guarda pares de valores- Memória não importa hoje em dia
Conserte o vale-presente
Esta versão às vezes usa o mesmo produto duas vezes: com o preço 50 e alvo 100, ela responde (0, 0). Descubra a causa comparando com o rastreamento acima e corrija. A função devolve as duas posições, a menor primeiro, ou None se não houver par.
def dois_somam(precos, alvo):
vistos = {}
for i, preco in enumerate(precos):
vistos[preco] = i
falta = alvo - preco
if falta in vistos:
return (vistos[falta], i)
return None
print(dois_somam([30, 50, 70], 100)) # esperado: (0, 2)- Encontra 30 + 70 = 100
- Preços repetidos funcionam: 50 + 50
- Não usa o mesmo produto duas vezes
- Sem par possível, devolve None
- Lista vazia devolve None
A versão corrigida em JavaScript, para vagas de frontend ou Node.js.
JavaScript
function doisSomam(precos, alvo) {
const vistos = new Map();
for (let i = 0; i < precos.length; i++) {
const falta = alvo - precos[i];
if (vistos.has(falta)) return [vistos.get(falta), i];
vistos.set(precos[i], i);
}
return null;
}Python
def dois_somam(precos, alvo):
vistos = {}
for i, preco in enumerate(precos):
falta = alvo - preco
if falta in vistos:
return (vistos[falta], i)
vistos[preco] = i
return NonePadrões 3 e 4: dois ponteiros e janela deslizante
Dois ponteiros para saber se uma palavra é um palíndromo (lida igual de trás para frente, como “arara”). Tempo O(n), espaço O(1).
Python
def eh_palindromo(texto):
esquerda, direita = 0, len(texto) - 1
while esquerda < direita:
if texto[esquerda] != texto[direita]:
return False
esquerda += 1
direita -= 1
return TrueJavaScript
function ehPalindromo(texto) {
let esquerda = 0;
let direita = texto.length - 1;
while (esquerda < direita) {
if (texto[esquerda] !== texto[direita]) return false;
esquerda++;
direita--;
}
return true;
}Você quer achar dois preços que somam 100 usando dois ponteiros: um no início, outro no fim, andando para o meio conforme a soma fica maior ou menor que o alvo. O que a lista precisa ter para isso funcionar?
- Estar ordenada
- Não ter números repetidos
- Ter um número par de itens
- Estar guardada num dicionário
A janela deslizante serve para perguntas sobre trechos seguidos: os 7 dias com mais vendas, as 3 horas com mais passageiros no ônibus. Em vez de somar cada trecho do zero, você soma o primeiro e depois “desliza”: entra o próximo valor, sai o mais antigo.
Maior soma de vendas em 2 dias seguidos. Cada deslize custa uma soma e uma subtração, não uma soma inteira.
vendas = [100, 200, 300, 50]
k = 2
soma = sum(vendas[:k])
melhor = soma
for i in range(k, len(vendas)):
soma += vendas[i] - vendas[i - k]
melhor = max(melhor, soma)
print(melhor)- Linha 1: Vendas de quatro dias.
- Linha 2: A janela tem 2 dias.
- Linha 3: A primeira janela, dias 0 e 1: 100 + 200 = 300.
- Linha 4: Por enquanto, a melhor janela é a primeira.
- Linha 6: Desliza: entra
vendas[2](300), saivendas[0](100). A soma vira 500, sem somar a janela de novo. - Linha 7: 500 é maior que 300: nova melhor janela.
- Linha 6: Desliza de novo: entra 50, sai 200. A soma cai para 350.
- Linha 8: O laço acabou. Tempo
O(n), não importa o tamanho da janela. Saída: 500
A melhor sequência de vendas
Complete maior_soma_janela(vendas, k) deslizando a janela dentro do laço. Trate os limites: se k for menor ou igual a zero, ou maior que a quantidade de dias (inclusive lista vazia), devolva None. Não some a janela inteira de novo a cada volta.
def maior_soma_janela(vendas, k):
soma = sum(vendas[:k])
melhor = soma
for i in range(k, len(vendas)):
# entra vendas[i], sai vendas[i - k]
pass
return melhor
print(maior_soma_janela([100, 200, 300, 50], 2)) # esperado: 500- Acha a melhor janela de 2 dias
- Acha a melhor janela de 3 dias
- Funciona com valores negativos (prejuízo)
- Lista vazia devolve None
- Janela maior que a lista devolve None
- Soma a lista inteira só uma vez, antes do laço
Escolher o padrão e explicar o custo
Qual padrão resolve cada problema de forma eficiente?
Contagem com dicionário · Busca com set ou dicionário · Dois ponteiros · Janela deslizante
- Descobrir a palavra mais repetida nos comentários de um produto
- Saber quantas viagens cada linha de ônibus fez no dia
- Checar se um CPF já está entre 2 milhões de cadastrados
- Achar dois produtos que fecham o vale-presente, numa lista fora de ordem
- Conferir se uma frase é palíndromo comparando as pontas
- Achar o par que soma o alvo numa lista já ordenada, sem memória extra
- Encontrar a semana (7 dias seguidos) com mais vendas no ano
- Maior média de passageiros em 3 horas consecutivas
Coloque em ordem uma boa explicação de complexidade durante a entrevista.
- Apresentar a solução direta e dizer o custo dela
- Apontar o gargalo: o trecho que se repete dentro do laço
- Propor a estrutura que elimina o gargalo, como um set ou dicionário
- Dizer o novo custo de tempo e o custo de espaço
- Testar com lista vazia, valores repetidos e limites
A pessoa entrevistadora pergunta: “sua solução é O(n). Ela é sempre mais rápida que a O(n²)?”. O que você responde?
Não necessariamente. Big O descreve como o custo cresce, não o tempo exato. Para listas pequenas, a versão com dois laços pode ser tão rápida quanto, e às vezes mais simples de ler. A O(n) ganha com folga quando a entrada cresce. Dizer isso mostra que você entende o que a notação mede, e quando vale a pena otimizar.
Fechamento
- Big O descreve como o trabalho cresce quando a entrada cresce:
O(1)não muda,O(log n)corta pela metade,O(n)acompanha,O(n²)explode. - Perguntar se um valor está numa lista é
O(n); numsetou dicionário, éO(1)em média, ao custo deO(n)de memória. - Contagem com dicionário e “lembrar o que já viu” transformam muitos problemas
O(n²)emO(n). - Dois ponteiros funcionam bem com pontas ou listas ordenadas; a janela deslizante resolve perguntas sobre trechos seguidos.
- Toda solução de entrevista termina com o custo de tempo e espaço explicado e testes com vazio, repetidos e limites.
Deduplique e busque, explicando o custo
Resolva dois problemas sobre uma coleção de verdade, como os contatos exportados do seu celular, uma lista de compras ou os dados de um projeto seu. Escreva as soluções em Python ou JavaScript e explique, em voz alta ou por escrito, como numa entrevista.
- Escreva uma função que remove itens repetidos mantendo a ordem, primeiro com lista e depois com
set - Escreva uma busca, como “dois valores que somam um alvo” ou “este item já existe?”, em versão direta e em versão com dicionário
- Diga a complexidade de tempo e de espaço de cada versão e qual foi o gargalo removido
- Teste cada função com lista vazia, itens repetidos, um único item e um caso sem resposta
- Gere uma lista com 100 mil números e compare o tempo das duas versões