Algoritmos e estruturas de dados

Ler notação Big-O: o que O(n log n) diz na prática

Big-O é a forma da curva de crescimento. O(n log n) escala; O(n²) colapsa quando a entrada cresce.

Quando trocar um loop de busca por um hash map

Muitas buscas na mesma coleção → Set/Map (O(1) por busca) em vez de scan O(n). Custo: memória do índice.

Cenário: par que soma um alvo num array ordenado

Array ordenado → dois ponteiros (início/fim), O(n) tempo e O(1) espaço. Sem ordem → hash set, O(n)/O(n).

Recursão, call stack e quando ela vira problema

Cada chamada empilha um frame; profundidade demais estoura a pilha e subproblemas repetidos explodem sem memoização.

Complexidade de espaço e o que conta como 'in-place'

Espaço = memória extra além da entrada. In-place = O(1) extra, mexendo no próprio array (mas recursão custa pilha).

Cenário: detectar ciclo numa lista encadeada

Floyd (fast/slow pointers): rápido anda 2, lento anda 1; se há ciclo eles colidem. O(n) tempo, O(1) espaço.

BFS x DFS: quando cada um

BFS: nível a nível com fila — caminho mais curto em grafo não-ponderado, 'o que está perto'. DFS: fundo com pilha/recursão — existência de caminho, ciclo, topo-sort, backtracking.

Programação dinâmica: memoização x tabulação

PD: subestrutura ótima + subproblemas sobrepostos (recursão que recalcula os mesmos args). Memoização: recursão + cache (fácil, calcula só o necessário). Tabulação: tabela bottom-up (sem recursão, mais rápida, espaço reduzível).

Cenário: maior subarray/substring com uma condição

Dois ponteiros formam uma janela válida; avança o fim, e quando invalida, avança o início até revalidar. Cada elemento entra/sai uma vez → O(n). Vale pra 'subarray contíguo com condição monotônica'.

Árvore binária de busca: quando O(log n) vira O(n)

Esquerda < nó < direita; busca descarta metade por passo → O(altura). Balanceada: altura ≈ log n. Dados ordenados numa BST simples viram lista torta → O(n). Daí AVL/rubro-negra.

Heap e fila de prioridade: o caso 'top K'

Heap: acesso O(1) ao extremo, insert/pop O(log n). Top K de N: min-heap de tamanho K, troca o topo quando entra algo maior. O(N log K) tempo, O(K) espaço, funciona em stream.

Ordenação estável e por que isso importa

Estável = empates mantêm a ordem de entrada. Importa pra ordenar por critérios em cascata (por data, depois por departamento): o sort instável embaralha os empates da passada anterior.

Complexidade amortizada: o array dinâmico

Cópias custam O(N) mas ficam cada vez mais raras; somadas dão O(N) pra N inserções → O(1) por inserção na média da sequência. Cuidado: um push isolado ainda pode ser O(N) (pico de latência).