Teu progresso
0 / 83 módulos0%
Estágio 01 · 01-05
BloqueadoAlgoritmos são as receitas de como resolver problemas computacionais. Linguagem, framework, banco, todos rodam algoritmos por baixo. Decisões arquiteturais frequentemente são, no fundo, decisões algorítmicas:
nested loop join, hash join, merge join baseado em estatísticas, você precisa entender os 3 pra ler EXPLAIN.Sem fundamento algorítmico, você vira escravo de bibliotecas, quando algo não tem lib, você trava.
Já vimos Big-O em 01-04. Reforçando:
Pra problemas, fala-se de:
Master theorem (pra recorrências de divide-and-conquer):
T(n) = a·T(n/b) + f(n), comparar f(n) com n^(log_b a) pra resolver.T(n) = 2T(n/2) + O(n) → O(n log n).Comparison-based sorts (têm lower bound Ω(n log n)):
| Algoritmo | Tempo médio | Pior caso | Espaço extra | Estável | Notas |
|---|---|---|---|---|---|
| Bubble sort | O(n²) | O(n²) | O(1) | sim | só didático |
| Insertion sort | O(n²) | O(n²) | O(1) | sim | bom pra n pequeno e quase-ordenado |
| Selection sort | O(n²) | O(n²) | O(1) | não | ruim, raramente usado |
| Merge sort | O(n log n) | O(n log n) | O(n) | sim | divide-and-conquer, boa pra dados externos |
| Quick sort | O(n log n) | O(n²) | O(log n) | não | excelente em prática, cache-friendly |
| Heap sort | O(n log n) | O(n log n) | O(1) | não | in-place mas constante alta |
| Tim sort | O(n log n) | O(n log n) | O(n) | sim | usado em Python, V8 (Array.sort) |
| Intro sort | O(n log n) | O(n log n) | O(log n) | não | quick → heap em recursão profunda; libstdc++ |
Non-comparison sorts (podem ser O(n) com restrições):
Array.prototype.sort em V8: Tim sort estável desde V8 7.0 (Chrome 70+, Node 11+). Use arr.sort((a,b) => a-b) pra numérico, (a,b) => a < b está errado (não estável).
Cuidado com binary search:
// Correto:
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2); // evita overflow
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
Erros clássicos: condição < vs ≤, off-by-one no mid, overflow em (lo+hi)/2 em linguagens com inteiro fixo.
Recursão: função se chama. Toda recursão tem caso base + passo recursivo.
function fib(n: number): number {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2); // O(2^n), exponencial
}
Problema: fib(40) repete cálculos massivamente.
Solução 1, Memoization (top-down DP):
const memo = new Map<number, number>();
function fib(n: number): number {
if (n < 2) return n;
if (memo.has(n)) return memo.get(n)!;
const r = fib(n - 1) + fib(n - 2);
memo.set(n, r);
return r;
}
// O(n) tempo, O(n) espaço
Solução 2, Tabulação (bottom-up DP):
function fib(n: number): number {
if (n < 2) return n;
let prev = 0, curr = 1;
for (let i = 2; i <= n; i++) {
[prev, curr] = [curr, prev + curr];
}
return curr;
}
// O(n) tempo, O(1) espaço
Quando DP se aplica:
Problemas DP clássicos:
Greedy: escolha localmente ótima → globalmente ótima (em alguns problemas). Exemplos:
Greedy só funciona se o problema tem matroid structure ou propriedade de troca. Senão dá errado (TSP greedy é ruim).
Divide-and-conquer: divide problema em sub-problemas independentes, resolve recursivamente, combina. Exemplos:
BFS (Breadth-First Search): O(V+E). Usa queue. Encontra menor número de arestas (shortest path em grafos não-ponderados).
DFS (Depth-First Search): O(V+E). Usa stack (recursão). Útil pra:
Dijkstra: O((V+E) log V) com heap. Caminho mais curto em grafo com pesos não-negativos. Greedy.
Bellman-Ford: O(V·E). Permite pesos negativos (mas não ciclos negativos).
Floyd-Warshall: O(V³). All-pairs shortest path. Pra grafos pequenos.
A*: Dijkstra + heurística admissível (subestima custo restante). Mais rápido na prática quando heurística é boa. Usado em jogos, GPS, sistemas de routing.
Topological sort: ordenação de DAG tal que aresta u→v aparece antes v. Útil pra build systems (dependências), scheduling, package managers.
Union-Find (DSU): estrutura pra "equivalence classes". Operações find, union em O(α(n)) amortizado (≈ O(1)). Usado em Kruskal MST, conexão de componentes em rede.
Minimum Spanning Tree (MST):
grep usa).Tries: estrutura natural pra prefix matching, autocomplete.
Suffix arrays e suffix trees: queries complexas em texto (subseqüências, repetições). Implementação avançada.
Pra você na prática: quando um problema é NP-hard (TSP, scheduling, knapsack), aceitar heurísticas/aproximações em vez de buscar solução exata. Algoritmos genéticos, simulated annealing, branch-and-bound, ML-based heurísticas, etc.
Pra passar o Portão Conceitual, sem consultar:
Implementar e comparar 3 algoritmos de routing num grafo de estradas reais.
.osm.pbf..osm.pbf (ou converta pra GeoJSON com osmium antes) e construa um grafo dirigido onde:
maxspeed da via).$ node route.js --from "lat1,lng1" --to "lat2,lng2" --algo dijkstra
graphhopper-js, etc).osm-pbf-parser, etc).Esse desafio é particularmente útil porque alimenta o capstone de logística.
Encerramento: após 01-05, você consegue olhar pra um problema novo e raciocinar: "isso parece grafo / DP / sorting / hashing / etc".
Threshold de Maestria
Acerte todas as 5 pra marcar o módulo como concluído. Sem pressa, sem timer. Tudo fica salvo no teu navegador.
Q1Você precisa do 'top-10 mais frequentes' em um dataset de 1 milhão de itens. Qual abordagem dá O(n log 10) em vez de O(n log n)?
Q2Você tem um grafo com pesos negativos (mas sem ciclos negativos) representando custos compostos. Por que Dijkstra não serve e o que usar?
Q3Memoization (top-down DP) e tabulação (bottom-up DP) resolvem os mesmos problemas. Qual diferença prática mais relevante?
Q4Qual destes problemas é NP-hard e portanto exige heurística/aproximação em escala de produção?
Q5Em A*, o que acontece se a heurística NÃO for admissível (i.e., superestima o custo restante)?
Destrava
01-05 é prereq dos seguintes módulos: