Glossário PT/EN 📖

Termos-chave do livro, com o original em inglês entre parênteses.

A–C

Algoritmo (algorithm) — conjunto de passos para resolver um problema.
Aresta (edge) — ligação entre dois nós de um grafo.
Array / Arranjo (array) — coleção de elementos guardados em posições contíguas na memória; acesso por índice em O(1).
Big-O — notação que descreve como o tempo/espaço cresce com a entrada.
Busca binária (binary search) — busca que divide a lista ordenada pela metade a cada passo; O(log n).
Busca em largura (breadth-first search, BFS) — explora o grafo por "camadas"; acha o caminho mais curto em grafos sem peso.
Caso-base (base case) — condição que para a recursão.
Caso-recursivo (recursive case) — parte em que a função chama a si mesma.
Colisão (collision) — quando duas chaves caem no mesmo slot da tabela hash.

Dividir para conquistar (divide and conquer, D&C) — técnica que quebra o problema em subproblemas menores do mesmo tipo (ex.: quicksort).
Fator de carga (load factor) — itens ÷ slots de uma tabela hash.
Fila (queue) — estrutura FIFO (primeiro a entrar, primeiro a sair); usada na BFS.
Função hash (hash function) — mapeia uma chave para um índice do array.
Grafo (graph) — conjunto de nós (vértices) ligados por arestas.
Grafo direcionado (directed graph) — arestas têm sentido (A → B).
Grafo ponderado (weighted graph) — arestas têm peso/custo.
Guloso (greedy) — algoritmo que escolhe a melhor opção local a cada passo.

Lista ligada (linked list) — elementos espalhados na memória, cada um apontando para o próximo; inserção/remoção O(1), acesso O(n).
Logaritmo (logarithm) — log₂ n ≈ "quantas vezes dá para dividir n por 2".
Memoização (memoization) — guardar resultados de subproblemas para não recalcular (programação dinâmica).
Mochila (knapsack problem) — problema clássico de programação dinâmica.
NP-completo (NP-complete) — classe de problemas sem solução eficiente conhecida; resolvidos por aproximação (ex.: caixeiro-viajante).
Nó / Vértice (node / vertex) — ponto de um grafo.
Pilha (stack) — estrutura LIFO (último a entrar, primeiro a sair).
Pilha de chamadas (call stack) — pilha onde o computador guarda as chamadas de função em andamento.
Pivô (pivot) — elemento escolhido no quicksort para particionar a lista.
Programação dinâmica (dynamic programming, DP) — resolver um problema combinando soluções de subproblemas sobrepostos.

Quicksort — algoritmo de ordenação por dividir-para-conquistar; O(n log n) médio.
Recursão (recursion) — função que chama a si mesma.
Selection sort (ordenação por seleção) — ordena escolhendo o menor repetidamente; O(n²).
Tabela hash (hash table) — mapeia chaves a valores; busca O(1) média. Em Python, é o dict.
Vetor — ver Array.