OrdenaçãoO(n²) → O(n log n)
Bubble/insertion são O(n²); quick/merge/heap são O(n log n). A diferença é a conta de comparações: ~5.000 vs ~660 em n=100.
// quick na média, heap no pior
sort.Slice(a, less) // introsort
Big-O & constantesassintótico
Big-O ignora constantes, mas elas decidem na prática: um O(n²) de constante magra (insertion, cache) ganha de um O(n log n) gordo em n pequeno.
Busca bináriaO(log n)
Ordenar desbloqueia busca em log n: 1M de itens em ~20 passos. Só vale se o array já está ordenado (custo amortizado em muitas buscas).
for lo <= hi { mid := (lo+hi)/2 }
Estabilidadeordem relativa
Sort estável mantém a ordem de chaves iguais · essencial pra ordenar por 2 critérios (nome, depois idade). Merge é estável; quick clássico não.
HashingO(1) médio
Hash table dá acesso O(1) na média via função de hash + bucket. Degrada pra O(n) com hash ruim ou ataque de colisão.
m := make(map[string]int)
Colisões & load factorrehash
Quando load factor (itens/buckets) passa do limite, a tabela cresce e faz rehash · O(n) pontual, amortizado O(1). Chaining vs open addressing.
Árvores & BSTO(log n)*
BST busca/insere em O(altura). Balanceada = log n; degenerada (inserção ordenada) vira lista encadeada = O(n).
BalanceamentoAVL · rubro-negra
Árvores auto-balanceadas (AVL, red-black) rotacionam pra manter a altura ~log n. É o que segura o pior caso da BST e sustenta índices B-tree.
Grafos: BFS vs DFSfila / pilha
BFS usa fila (camadas, caminho mínimo em grafo sem peso); DFS usa pilha/recursão (ciclos, topológico, componentes).
// BFS q := []int{src} // DFS func dfs(v)
Travessias & caminhoDijkstra
Caminho mínimo com peso: Dijkstra (heap, sem peso negativo). Sem peso: BFS basta. Custo é a soma das arestas, não o nº de saltos.