O que este curso é e como usá-lo
Este é o quinto curso de Ciência da Computação Universitária: estruturas de dados e algoritmos — os recipientes aos quais um programa recorre e as receitas que os percorrem, escolhidas pelo seu custo.
Limites de escopo, declarados uma vez: curso de estudo, não grau; Python 3 é do veículo, cada fragmento é original, e toda afirmação de custo neste material foi verificada contando operações nos conjuntos de dados exatos impressos aqui.
- A unidade 5.1 é a régua: como o custo cresce.
- Unidades 5.2–5.5 são os recipientes: listas lineares, tabelas hash, árvores, grafos.
- Unidades 5.6–5.7 são as receitas: ordenação e busca.
O hábito de medição: nunca confie em uma afirmação de custo que não tenha contado — cada unidade fixa um conjunto de dados, e a suíte rederiva cada número.
Análise assintótica
Por que importa. Escolher entre duas soluções é escolher entre suas taxas de crescimento: em $n = 1000$, a diferença entre $n \log n$ e $n^2$ é um fator de aproximadamente $100$.
A ideia, com uma imagem. Big-O é um limite superior até uma constante: $f(n) = O(g(n))$ quando $f(n) \le c\,g(n)$ para grandes $n$. Big-Ω é o par do limite inferior, Big-Θ a taxa exata. Descarte constantes e termos de ordem inferior: $3n^2 + 5n + 7$ é $\Theta(n^2)$ — o termo $n^2$ consome o resto à medida que $n$ cresce.
| $n$ | $\log_2 n$ | $n$ | $n\log_2 n$ | $n^2$ | $2^n$ |
|---|---|---|---|---|---|
| 10 | 3 | 10 | 33 | 100 | 1 024 |
| 100 | 7 | 100 | 664 | 10 000 | $\approx 10^{30}$ |
| 1000 | 10 | 1000 | 9 966 | $10^6$ | $\approx 10^{301}$ |
A dedução (por que log n para divisão pela metade). Cada divisão da entrada deixa um passo: um algoritmo que divide $n$ pela metade a cada etapa toca $\log_2 n$ níveis — busca binária em $n = 16$ faz no máximo $4$ sondagens porque $2^4 = 16$. E $\log$ de um milhão é cerca de $20$: a planicidade é o motivo pelo qual algoritmos em tempo logarítmico parecem instantâneos.
Exemplo resolvido 1 — contar vale mais que adivinhar. Dois laços sobre a mesma matriz de $n = 100$ itens: o laço único executa seu corpo $100$ vezes; o aninhado $100 \times 100 = 10\,000$ vezes. Dobrar $n$ para $200$: o corpo linear duplica para $200$, os quadruplos aninhados para $40\,000$ — o razão medida $4 = 2^2$ é o expoente, lido nos dados.
Exemplo resolvido 2 — lendo código como uma classe. Um laço que reduz pela metade
i = i // 2: $\Theta(\log n)$ passos. Dois laços sequenciais sobre $n$: os
custos somam, $\Theta(n) + \Theta(n) = \Theta(n)$. Um laço dentro de um
laço de redução pela metade: eles multiplicam, $\Theta(n \log n)$ — a forma do merge sort.
Erros comuns. Ler Big-O como garantia de velocidade (constantes importam em pequenos $n$). Esquecer o layout da entrada: $O(1)$ indexação é uma propriedade de array, não de lista ligada. Reportar o melhor caso quando o pior caso foi solicitado.
Resumo. Limites O acima, Ω abaixo, Θ fixa a taxa; elimine constantes e termos de menor ordem; meça por duplicação e leia o expoente.
Listas, pilhas e filas
Por que importa. As estruturas lineares são os recipientes padrão, e seus custos diferem nas extremidades: saber qual extremo é barato é o assunto inteiro.
A ideia, com uma imagem. Uma lista Python é um array contíguo : índice $i$ calcula um endereço, $O(1)$; inserir na frente move tudo, $O(n)$. Uma lista ligada troca o salto por cortes baratos: cada nó carrega um ponteiro para o próximo. Um pilha adiciona e remove em uma extremidade (LIFO); a fila adiciona em uma extremidade, remove na outra (FIFO).
Derivação (por que append é amortizado O(1)). O array cresce dobrando: adicionar $n$ itens copia cada elemento no máximo uma vez em total entre todos os redimensionamentos — cópias totais $\le 2n$ para $n$ adições, portanto a adição média é constante mesmo quando um redimensionamento copia $n$. Inserir na posição $0$ nunca se amortiza: toda chamada desloca todos $n$ residentes, então $n$ inserções frontais movem $\Theta(n^2)$ elementos (medido: a contagem de operações quadruplica quando $n$ dobra).
Exemplo resolvido 1 — rastreamento de pilha. push 3, push 7, push 1, depois
pop, pop: os pops retornam $1$ depois $7$ — último a entrar, primeiro a sair. O
uso clássico são colchetes balanceados: escanear ([]){}, empilhando aberturas;
cada fechador deve corresponder ao topo — a string está balanceada, enquanto ([)]
falha porque ) encontra [ no topo.
Exemplo resolvido 2 — rastreamento de fila. Enqueue a, b, c; dois dequeues
retornam a depois b; a frente é c. Primeiro a entrar, primeiro a sair. Duas pilhas
podem simular uma fila (bandeja de entrada e saída, cada elemento processado duas vezes), o que
faz com que collections.deque — uma lista duplamente encadeada — sirva ambas as extremidades em
$O(1)$.
Erros comuns. Usar list.pop(0) em um loop ($O(n)$ cada; use
deque.popleft()). Busca em lista encadeada por índice (percorra a cadeia,
$O(n)$). Assumindo que a lista Python é encadeada — ela é um array.
Resumo. Array: $O(1)$ índice, $O(n)$ inserção na frente. Encadeada: $O(1)$ splice após um nó localizado. Pilha uma extremidade, fila duas; deque faz ambas as extremidades em $O(1)$.
Hashing
Por que importa. Uma tabela hash é a estrutura que responde membroship em uma etapa esperada — o motor dentro de conjuntos, dicionários e caches.
A ideia, com uma imagem. Uma função hash mapeia uma chave para um balde: $h(k) = k \bmod 13$ envia $4, 17, 30, 43$ todos para o balde $4$ — uma colisão. Encadeamento pendura uma lista em cada balde; endereçamento aberto percorre até o próximo slot livre (probing linear: $17 \to 5$, $30 \to 6$, $43 \to 7$).
A dedução (o fator de carga rege a cadeia). Com $m$ baldes e $n$ chaves, o fator de carga $\alpha = n/m$ também é o comprimento médio da cadeia: nossas chaves fixas $[4, 17, 30, 43, 12, 25, 38]$ dão $\alpha = 7/13 \approx 0.54$, com balde $4$ contendo $4$ chaves, balde $12$ contendo $3$, e onze baldes vazios. Custo de busca bem-sucedido é cerca de comparações $1 + \alpha/2$ com encadeamento; cresce $m$ com $n$ e o o custo esperado permanece $O(1)$ — é por isso que os dicionários mantêm velocidade.
Exemplo resolvido 1 — cadeias exatas. Insira $4, 17, 30, 43$ com $h(k) = k \bmod 13$: cada chave gera hash para $4$, logo a cadeia lê $4 \to 17 \to 30 \to 43$. Buscar $43$ percorre $4, 17, 30, 43$: quatro comparações — o pior caso que uma tabela com essa carga pode gerar, e exatamente o que a função de espalhamento uniforme evita em média.
Exemplo resolvido 2 — sondagem no mesmo conjunto. Endereçamento aberto com prospecção linear: $4$ ocupa a posição $4$; $17$ verifica $4$ (ocupada) $\to 5$; $30$ verifica $4, 5 \to 6$; $43$ verifica $4, 5, 6 \to 7$. Total de verificações: $1 + 2 + 3 + 4 = 10$ para quatro inserções — aglomeração cresce as sequências, que é por isso que tabelas reais mantêm $\alpha$ abaixo de aproximadamente $0.75$ e por que a ordem de sondagem importa.
Erros comuns. Usar módulo de potência de dois quando chaves compartilham bits baixos (escolha um primo). Alterar uma chave enquanto está na tabela (seu hash movimentações). Esperando-se o pior caso de $O(1)$ — essa garantia exige uma perfeita ou bucket tipo árvore.
Resumo. Hash espalha chaves; colisões são normais, então escolha o resolução (encadeamento ou prospecção); $\alpha = n/m$ prediz o custo; redimensionar para mantê-lo constante.
Árvores e montículos
Por que importa. Árvores reduzem os custos logarítmicos ao dividir o trabalho restante pela metade em cada nível — busca, inserção e (para heaps) mínimo/máximo em $O(\log n)$.
A ideia, com uma imagem. Uma árvore binária de busca mantém o invariante de ordem: subárvore esquerda $<$ nó $<$ subárvore direita. Inserindo $50, 30, 70, 20, 40, 60, 80$ constrói uma árvore perfeita de altura $2$; a percurso em ordem lê $20, 30, 40, 50, 60, 70, 80$ — ordenado, por construção. Um heap é uma árvore completa armazenada em um array: filhos do índice $i$ estão em $2i+1$ e $2i+2$; um min-heap mantém cada pai $\le$ seus filhos, então o mínimo reside no índice $0$.
A derivação (a altura é o custo). Uma árvore perfeita de altura $h$ contém $2^{h+1} - 1$ nós: $7$ em $h = 2$, $15$ em $h = 3$, $31$ em $h = 4$ — então $n$ nós precisam de altura $\lfloor \log_2 n \rfloor$ quando equilibrados, e todo caminho da raiz à folha (busca, inserção, deslize) paga essa altura. Desequilíbrio causa falha: inserir chaves ordenadas $1, 2, 3, 4$ forma uma cadeia de altura $3 = n - 1$ — $O(n)$ busca, razão pela qual variantes equilibradas (AVL, vermelho-negro) rotacionam para manter a complexidade logarítmica.
Exemplo resolvido 1 — busca e inserção na BST. Buscar $40$: comparar $50$ (direita tem chaves menores — ir à esquerda), $30$ (ir à direita), $40$ — encontrado em $3$ comparações contra $7$ nós: a contagem de níveis. Inserir $35$: percorra o mesmo caminho, pendure à esquerda de $40$; a percorrência em ordem agora lê $20, 30, 35, 40, 50, 60, 70, 80$ — ainda ordenado.
Exemplo resolvido 2 — elevação de chave no heap. Construa um min-heap inserindo
$5, 3, 8, 1$: $5$ pousa no índice $0$; $3$ sobe sobre $5$; $8$ permanece;
$1$ sobe sobre $5$ e depois sobre $3$, pousando no índice $0$. O array
lê $[1, 3, 8, 5]$ — pai $\le$ filho em tudo (verifique: $1 \le 3,
8$; $3 \le 5$). heapq.heapify builds the whole array in $O(n)$ por
descida de chave a partir do meio.
Erros comuns. Esquecer que o heap é apenas semiordenado (uma percorrência em ordem de $[1, 3, 8, 5]$ não tem sentido; apenas a raiz é especial). Esperar equilíbrio de BST por sorte aleatória com entrada ordenada. Armazenar uma árvore de $n$ nós em $n+1$ posições de array e errar na fórmula de cálculo dos filhos.
Resumo. BST: invariante de ordem, percorrência em ordem = ordenado, custo = altura, $\log$ quando equilibrado. Montículo: forma completa em um array, pai domina os filhos, raiz é o mínimo em $O(1)$, custeio de deslize igual à altura.
Grafos e travessia
— é um grafo, e as duas travessias são as sondas que respondem à alcançabilidade, — é um grafo, e as duas travessias são as verificações que respondem à alcançabilidade, camadas e estrutura.
A ideia, com uma imagem. Um grafo $G = (V, E)$: nosso curso fixo grafo possui $V = \{A \ldots H\}$ ($8$ nós) e $10$ arestas não direcionadas: $AB, AC, BD, CD, CE, DF, EF, EG, FH, GH$. A lista de adjacência armazena, por nó, seus vizinhos ($20$ entradas para $10$ arestas não direcionadas); a matriz de adjacência é uma $8 \times 8$ grade de $64$ células, $1$ em uma aresta.
A dedução (por que O(V+E)). Busca em largura e profundidade marcam cada nó uma vez (trabalho $V$) e escaneiam cada aresta armazenada uma vez (trabalho $E$): $O(V + E) = O(8 + 10)$ visitas no grafo do curso. A matriz paga $O(V^2)$ porque cada linha percorre todas as colunas $8$, com ou sem aresta — o vence na lista em grafos esparsos ($E \ll V^2$), a matriz vence quando o grafo é denso ou a questão é apenas uma consulta de célula única.
Exemplo resolvido 1 — BFS por camadas. De $A$ com vizinhos visitados alfabeticamente: camada 0 é $A$; camada 1 é $B, C$; camada 2 é $D, E$; camada 3 é $F, G$; camada 4 é $H$. A ordem completa lê-se $A, B, C, D, E, F, G, H$, e a camada de um nó é sua menor distância não ponderada a partir de $A$ — é isso que uma fila oferece: a fronteira saem em ordem de chegada.
Exemplo resolvido 2 — DFS por pilha. De $A$, percorrendo vizinhos alfabeticamente: $A \to B \to D$; o próximo vizinho não visitado de $D$ é $C$; $C \to E$; $E \to F$; $F \to H$; o vizinho não visitado de $H$, $G$, encerra a caminhada. A ordem é $A, B, D, C, E, F, H, G$ — uma caminhada profunda que retrocede em pontos sem saída. Mesmo grafo, mesma $O(V+E)$, formato diferente: BFS responde saltos mínimos, DFS expõe caminhos e ciclos.
Erros comuns. Esquecer marcar como visitado (loop infinito em qualquer ciclo). Interpretar camada do BFS como distância ponderada (não ponderado — pesos exigem Dijkstra). Armazenar arestas não direcionadas uma vez na matriz (ambas as células $[u][v]$ e $[v][u]$ devem ser definidas).
Resumo. Lista para esparsa, matriz para densa; ambas as travessias são $O(V+E)$; a fila fornece camadas e saltos mínimos, a pilha fornece caminhos profundos.
Ordenação
Por que importa. Ordenação é pré-condição para busca binária, eliminação de duplicatas e fusão — e lição canônica em análise de custo: mesma tarefa, contas muito diferentes.
A ideia, com ilustração. O conjunto de dados do curso é $[5, 2, 9, 1, 7, 3]$. Inserção cresce um prefixo ordenado, deslizando cada nova carta para trás: após passar por $1$, o prefixo lê-se $1, 2, 5, 9$. Fusão divide ao meio, ordena cada metade, funde. Quicksort particiona em torno de um pivô. OBubble sort troca adjacentes inversões — educativo, raramente usado.
A derivação (a contagem de inversões). Uma inversão é um par fora de ordem. No conjunto de dados do curso, as inversões são $(5,2), (5,1), (5,3), (2,1), (9,1), (9,7), (9,3), (7,3)$ — oito pares. Cada troca adjacente corrige exatamente uma inversão, então qualquer ordenação por trocas adjacentes faz exatamente $8$ trocas aqui; as deslocamentos da inserção iguam às inversões também. Merge sort conta as mesmas inversões durante suas fusões enquanto move cada elemento no máximo $\log_2 6 \approx 2.6$ levels: $O(n \log n)$ beats $O(n^2)$ porque corrige muitas inversões por movimento.
Exemplo resolvido 1 — inserção à mão. $[5, 2, 9, 1, 7, 3]$: insere $2$ (um deslocamento: $5, 2 \to 2, 5$); $9$ anexa (nenhum deslocamento); $1$ desloca três ($[1, 2, 5, 9]$); $7$ passa por $9$ apenas (um deslocamento, prefixo $[1, 2, 5, 7, 9]$); $3$ desloca três. Deslocamentos totais $1 + 0 + 3 + 1 + 3 = 8$ — exatamente a contagem de inversões — com $11$ comparações (cada passagem termina com uma comparação falha), e o resultado ordenado $[1, 2, 3, 5, 7, 9]$.
Exemplo resolvido 2 — merge sort nos mesmos dados. Divida por dois $[5, 2, 9]$ and $[1, 7, 3]$; recursively $[2, 5, 9]$ and $[1, 3, 7]$; mesclar: $1, 2, 3, 5, 7, 9$. A contagem de comparações medida é $10$ nesta entrada, contra a inserção de $11$ — próximo aqui, mas as famílias divergem: em $n = 1000$, $n \log_2 n \approx 9\,966$ contra $n^2 = 10^6$, um fator de aproximadamente $100$.
Erros comuns. Chamar o pior caso do quicksort de raro e esquecer que entrada ordenada com pivô no primeiro elemento É o pior caso ($O(n^2)$). Esperar que o heapsort seja estável (não é; o merge sort é). Contar apenas comparações quando movimentos dominam em registros grandes.
Resumo. Ordens por troca adjacentes pagam uma move por inversão (pior caso de $\Theta(n^2)$); divide-e-conquista paga $\Theta(n \log n)$; estabilidade sobrevive no merge e na inserção, não no quick ou heap.
Busca
Por que importa. Pertencimento e consulta são as operações mais executadas em programas reais — a diferença entre $16$ verificações e $4$ é o diferença entre linear e binária em uma página de dados.
A ideia, com uma imagem. Busca linear percorre o array: $O(n)$, sem pré-condições. Busca binária reduz pela metade um intervalo ordenado: compara o meio, mantém metade. No array ordenado de $16$ itens $[3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63]$ (indices $0$–$15$), searching $43$ probes indices $7, 11, 9, 10$ — value $31$, then $47$, then $39$, then $43$: quatro sondagens, encontradas.
A derivação (o limite de sondagem). Cada sondagem reduz pela metade os candidatos: após $k$ sondagens restam no máximo $\lceil n / 2^k \rceil$, então o pior caso é $\lceil \log_2(n+1) \rceil$ sondagens — para $n = 16$ isso é $5$ (e nosso acerto levou $4$). O linear paga $16$ na extremidade e $16$ mais por cada falha além do fim; o binário paga o mesmo $\le 5$ para cada consulta. A pré-condição é a ordenação: em dados não ordenados o argumento de divisão collapses, e apenas o linear permanece honesto.
Exemplo resolvido 1 — a trilha de sondagem. Busca $43$: $lo=0$, $hi=15$, $mid=7$ lê $31 < 43$ logo $lo=8$; $mid=11$ lê $47 > 43$ logo $hi=10$; $mid=9$ lê $39 < 43$ logo $lo=10$; $mid=10$ lê $43$ — encontrado no índice $10$ após $4$ sondagens. Compare: percursos lineares $11$ valores para alcançar o índice $10$.
Exemplo resolvido 2 — a falha que prova o limite. Busca $64$ (ausente, acima do fim): binário sonda $7 (31), 11 (47), 13 (55), 14 (59), 15 (63)$ — cinco sondagens, depois o intervalo vazio reporta ausente. O linear percorreria todos os $16$ e reportaria o mesmo ausente — a falha custa ao binário seu pior caso e ao linear sua matriz completa, e a lacuna ainda cresce com $\log$ versus $n$.
Erros comuns. Busca binária em dados não ordenados (errado silenciosamente,
respostas, não falhas). Erro de um na atualização (lo = mid em vez de
mid + 1 loop infinito). Calcular mid como $(lo + hi) / 2$ em linguagens
com overflow de largura fixa (lo + (hi - lo) // 2 é seguro).
Resumo. Linear: sem pré-condição, $O(n)$. Binária: dados pré-condição ordenada, $\lceil \log_2(n+1) \rceil$ sondagens no pior caso — $16$ slots resolvidos em até $5$.