Complexidade, vetores e busca
Dois programas podem dar a mesma resposta e um deles levar horas. Hoje vamos entender como os dados ficam na memória, como medir o custo de um algoritmo sem cronômetro e por que procurar em dados ordenados é tão mais rápido.
Navegação: ← → trocam de etapa · V alterna entre etapas e página única · M sumário · F tela cheia · + − tamanho do texto · dentro do código, Ctrl+Enter executa.
Todo código desta aula pode ser editado e executado aqui mesmo. Altere os exemplos à vontade; o botão ↺ restaura o original. Suas alterações ficam salvas neste navegador; em Progresso você pode baixá-las em um arquivo e continuar em outro computador.
As visualizações mostram os algoritmos passo a passo: altere os dados, use Próximo passo ou Animar. Nos exercícios, o botão ✓ Verificar testa seu código com várias entradas.
Por que estudar estruturas de dados?
Uma estrutura de dados é uma forma de organizar dados na memória para que certas operações fiquem rápidas: buscar, inserir, remover, pegar o menor…
O exemplo ao lado faz as mesmas 100 consultas em uma lista e em um conjunto (set) com os mesmos 10 mil números. A resposta é igual; o tempo, não.
Não existe estrutura melhor em tudo. Cada uma acelera algumas operações e cobra em outras. Ao longo da disciplina, vamos aprender a medir esse custo e a escolher.
Vetor: elementos lado a lado na memória
Um vetor (array) guarda seus elementos em posições consecutivas da memória, todas do mesmo tamanho. Por isso o computador calcula o endereço de qualquer posição com uma única conta.
endereço(v[i]) = início + i × tamanho_do_elemento
Não importa se o vetor tem 6 ou 6 milhões de elementos: acessar v[i] custa sempre o mesmo. Dizemos que o acesso é O(1), tempo constante.
É também por isso que os índices começam em 0: o índice é o deslocamento a partir do início.
list é um vetor de referências: as posições consecutivas guardam endereços dos objetos. Os elementos podem ter tipos diferentes, mas o acesso por índice continua O(1). Em C, um int v[6] guarda os próprios números lado a lado.Inserir e remover no meio custa caro
Como os elementos ficam colados, não há “espaço livre” entre eles. Para inserir no meio, é preciso deslocar todos os que vêm depois.
Inserir na posição p de um vetor com n elementos desloca n − p elementos. No pior caso (início), desloca todos: O(n).
No fim, não desloca nenhum: O(1). Remover segue a mesma lógica.
Operação em list | Custo |
|---|---|
v[i], v[i] = x | O(1) |
v.append(x), v.pop() | O(1) amortizado |
v.insert(0, x), v.pop(0) | O(n) |
x in v, v.index(x) | O(n) |
range(pos + 1, len(v)) e veja o que acontece com os valores.Vetor dinâmico: por que append é rápido
Um vetor de verdade tem tamanho fixo. A list do Python é um vetor dinâmico: reserva mais espaço (capacidade) do que usa (tamanho).
Quando enche, cria um vetor maior e copia tudo para lá. No código ao lado, o novo vetor tem o dobro da capacidade (o CPython cresce só cerca de 12,5% por vez; o que importa é crescer por um fator, não por uma quantidade fixa). Essa cópia é cara, O(n), mas acontece cada vez mais raramente.
Dobrando, a soma de todas as cópias fica abaixo de 2n: cada append custa em média menos de 2 cópias. Dizemos que é O(1) amortizado.
self.capacidade + 1 (cresce de um em um) e compare o número de cópias.Matrizes na memória
A memória é uma fila única de posições. Uma matriz L × C é guardada linha após linha: o elemento m[i][j] fica na posição i × C + j desse vetor.
Na matriz 3 × 4 acima, m[2][1] está na posição 2 × 4 + 1 = 9 da memória: antes dele há 2 linhas inteiras (8 elementos) e mais 1 elemento.
Assim, acessar m[i][j] também é O(1). Percorrer a matriz inteira visita L × C elementos: O(L·C), ou O(n²) se for quadrada.
int m[3][4] é exatamente isso: 12 inteiros seguidos. Em Python, uma lista de listas é um vetor de referências para as linhas.Quanto custa um algoritmo?
Medir em segundos depende do computador, da linguagem e do que mais está rodando. Para comparar algoritmos, contamos quantas operações básicas eles fazem em função do tamanho da entrada, n.
Operação básica: uma comparação, uma soma, uma atribuição, um acesso a v[i]. Cada uma custa um tempo constante.
No exemplo, soma faz uma operação por elemento: n. pares compara cada elemento com todos: n × n.
Medindo o tempo de verdade
O tempo medido varia a cada execução, mas a proporção revela o comportamento: dobre n e veja quanto o tempo cresce.
| Se o algoritmo é… | dobrar n multiplica o tempo por |
|---|---|
| O(n) | ≈ 2 |
| O(n²) | ≈ 4 |
| O(n³) | ≈ 8 |
| O(log n) | quase nada (soma uma constante) |
time.perf_counter() devolve um relógio de alta precisão, em segundos.
Como as funções crescem
Para n pequeno, quase tudo é rápido. A diferença aparece quando n cresce: a taxa de crescimento domina qualquer constante.
Notação O grande
Dizemos que um algoritmo é O(f(n)) quando, para n grande, ele faz no máximo algo proporcional a f(n) operações. É um limite superior do crescimento.
Como simplificar
- Ignore constantes multiplicativas: 3n + 5 → O(n).
- Fique só com o termo que cresce mais rápido: n² + 100n + 7 → O(n²).
- A base do logaritmo não importa: log₂ n e log₁₀ n diferem por uma constante → O(log n).
| Classe | Exemplo típico |
|---|---|
O(1) | acessar v[i], append |
O(log n) | busca binária |
O(n) | percorrer uma lista, busca sequencial |
O(n log n) | merge sort, sorted() |
O(n²) | dois laços aninhados sobre os dados |
O(2ⁿ) | testar todos os subconjuntos |
Regras práticas para analisar código
| Estrutura do código | Custo |
|---|---|
| comandos em sequência | soma os custos (fica o maior) |
| laço que roda n vezes | n × custo do corpo |
| laços aninhados (n e n) | n × n = n² |
| laço que divide por 2 a cada volta | log n |
| chamada de função | custo da função (cuidado com in, index, insert, sorted…) |
Por que dividir pela metade dá log n? Começando em n, depois de k divisões sobra n / 2ᵏ. Chega a 1 quando 2ᵏ = n, ou seja, k = log₂ n.
Melhor caso, pior caso e caso médio
O mesmo algoritmo pode trabalhar mais ou menos dependendo dos dados. Na busca sequencial em n elementos:
| Caso | Quando acontece | Comparações |
|---|---|---|
| melhor | alvo na primeira posição | 1 → O(1) |
| pior | alvo no fim ou ausente | n → O(n) |
| médio | alvo em posição aleatória | ≈ n/2 → O(n) |
Normalmente analisamos o pior caso: é uma garantia. Se o pior caso é aceitável, qualquer entrada será.
Qual é a complexidade?
Leia o trecho, decida a ordem de crescimento em função de n (o tamanho de v) e só então clique.
Busca sequencial
A estratégia mais simples: olhar um elemento de cada vez, do início ao fim, até achar o alvo ou acabar o vetor. Funciona com qualquer vetor, ordenado ou não.
Convenção usada em toda a disciplina: a função devolve a posição do alvo, ou -1 se ele não estiver no vetor.
Custo: O(n) no pior caso. É o que o Python faz em x in lista e lista.index(x).
Busca binária
Se o vetor está ordenado, dá para fazer como num dicionário de papel: abrir no meio e descartar a metade onde a palavra não pode estar.
- Mantenha o trecho ainda possível entre
iniefim. - Olhe o elemento do
meio. - Se for o alvo, achou. Se for menor, o alvo está à direita:
ini = meio + 1. Se for maior, está à esquerda:fim = meio - 1. - Se
inipassar defim, o trecho ficou vazio: não está no vetor.
Cada comparação corta o trecho pela metade: no pior caso, O(log n) comparações.
Teste de mesa da busca binária
Acompanhe ini, fim e meio a cada linha. Antes de avançar, tente prever o próximo valor de meio.
Sequencial × binária: quantas comparações?
O programa conta as comparações no pior caso da busca sequencial (alvo no fim) e da binária, para vetores cada vez maiores.
| n | sequencial (pior) | binária (pior) |
|---|---|---|
| 1.000 | 1.000 | 10 |
| 1.000.000 | 1.000.000 | 20 |
| 1.000.000.000 | 1.000.000.000 | 30 |
Cuidados com a busca binária
Erros comuns
- Vetor fora de ordem: o algoritmo não reclama, só devolve a resposta errada.
while ini < fimem vez de<=: deixa de olhar o trecho de um elemento só.ini = meioem vez demeio + 1: pode ficar preso para sempre no mesmo trecho.
Pronto no Python: bisect
bisect_left(v, x) devolve a posição onde x está ou deveria ser inserido para manter a ordem. insort(v, x) insere mantendo a ordem (a busca é O(log n), mas a inserção ainda desloca: O(n)).
Desafio: raiz quadrada com busca binária
A busca binária não serve só para vetores. Ela funciona em qualquer intervalo onde a resposta “sim/não” muda uma única vez.
Encontre a raiz quadrada inteira de n: o maior r tal que r * r <= n. Não use math nem ** 0.5.
Para n = 1000000, a resposta é 1000. Quantos passos seu programa precisou? Compare com testar r = 0, 1, 2, … um por um.
Mostrar uma solução
Qual será a saída?
Leia o código, escreva sua resposta e só então clique. Errou? Copie o código para o laboratório e execute.
Prática 1: vetores
Escreva sua solução no editor. ▶ Executar roda com a entrada que você quiser; ✓ Verificar roda os testes automáticos e mostra o que falta. Tente antes de abrir a solução!
1. Segundo maior básico
Leia números inteiros na mesma linha e mostre o segundo maior valor distinto. Se não existir (todos iguais), mostre Não existe. Percorra a lista uma única vez, sem ordenar: O(n).
| Entrada | Saída esperada |
|---|---|
5 9 2 7 | Segundo maior: 7 |
4 4 4 | Não existe |
Mostrar uma solução
2. Inserir mantendo a ordem básico
Leia um vetor ordenado (primeira linha) e um valor x (segunda linha). Insira x mantendo a ordem, sem usar sort(), sorted() nem insert(): coloque-o no fim e desloque os maiores para a direita. Mostre o vetor e quantos elementos foram deslocados. Valores iguais a x não se movem.
| Entrada | Saída esperada |
|---|---|
1 3 5 7 4 | Resultado: [1, 3, 4, 5, 7] Deslocamentos: 2 |
Mostrar uma solução
Prática 2: busca binária
Nos dois exercícios, a primeira linha é um vetor de inteiros em ordem crescente e a segunda, o valor procurado.
3. Busca binária passo a passo médio
Faça a busca binária mostrando, a cada volta, ini=… fim=… meio=…. Ao final, mostre Encontrado na posição P ou Não encontrado, e o total de voltas em Passos: K. Use meio = (ini + fim) // 2.
| Entrada | Saída esperada |
|---|---|
1 3 5 7 9 11 13 11 | ini=0 fim=6 meio=3 ini=4 fim=6 meio=5 Encontrado na posição 5 Passos: 2 |
Mostrar uma solução
4. Primeira ocorrência médio
O vetor pode ter valores repetidos. Mostre a posição da primeira ocorrência do alvo (Primeira posição: P) ou Não encontrado. Use busca binária: ao achar o alvo, guarde a posição e continue procurando à esquerda. Não use index().
| Entrada | Saída esperada |
|---|---|
1 2 2 2 3 5 2 | Primeira posição: 1 |
Mostrar uma solução
Prática 3: eficiência
Os dois problemas têm uma solução óbvia e lenta (testar todas as combinações). Encontre a solução que aproveita a ordem dos dados.
5. Par com soma médio
Leia um vetor em ordem crescente e um alvo. Encontre dois elementos de posições diferentes cuja soma seja o alvo e mostre Par: a + b (menor primeiro), ou Nenhum par. Testar todos os pares é O(n²); use dois índices, um em cada ponta, e resolva em O(n).
| Entrada | Saída esperada |
|---|---|
1 2 4 7 11 15 15 | Par: 4 + 11 |
Mostrar uma solução
6. Busca em matriz ordenada desafio
Leia L C, depois L linhas com C inteiros e, por fim, o alvo. Cada linha cresce da esquerda para a direita e cada coluna cresce de cima para baixo. Mostre Encontrado em (i, j) ou Não encontrado.
Dica: comece no canto superior direito. Se o valor for maior que o alvo, a coluna inteira pode ser descartada; se for menor, a linha inteira. Isso dá O(L + C), contra O(L × C) de olhar tudo.
Mostrar uma solução
Laboratório livre
Espaço para testar ideias durante a aula. Sugestões: meça o tempo de v.insert(0, x) e de v.append(x) para 10 mil elementos; conte quantas comparações a busca binária faz para cada alvo de um vetor de 16 elementos; compare x in lista com x in conjunto para n cada vez maior.