📚 Teoria de Algoritmos - Catálogo Completo
Ordenação | Estruturas de Dados | Grafos | Programação Dinâmica | IA | Investigação Operacional
Plataforma de Ensino de Estruturas de Dados e Algoritmos
Ordenação | Estruturas de Dados | Grafos | Programação Dinâmica | IA | Investigação Operacional
| Método | Pior | Médio | Melhor | Estável? | In-place? |
|---|---|---|---|---|---|
| Insertion Sort | O(n²) | O(n²) | Ω(n) | ✅ | ✅ |
| Selection Sort | O(n²) | O(n²) | Ω(n²) | ❌ | ✅ |
| Bubble Sort | O(n²) | O(n²) | Ω(n) | ✅ | ✅ |
| Shellsort | O(n^(3/2)) | — | Ω(n log n) | ❌ | ✅ |
| Merge Sort | O(n log n) | Θ(n log n) | Ω(n log n) | ✅ | ❌ |
| Quick Sort | O(n²) | Θ(n log n) | Ω(n log n) | ❌ | ✅ |
| Heap Sort | O(n log n) | Θ(n log n) | Ω(n log n) | ❌ | ✅ |
| Counting Sort | O(n+k) | Θ(n+k) | Ω(n+k) | ✅ | ❌ |
Explora o grafo por níveis usando uma fila (Queue). Encontra o caminho com menos arestas.
Complexidade: O(V + E)
Aplicação: Redes sociais, web crawling
Explora até o fim usando uma pilha (Stack). Útil para deteção de ciclos.
Complexidade: O(V + E)
Aplicação: Ordenação topológica, labirintos
Encontra o caminho mais curto em grafos com pesos não negativos.
Complexidade: O((V+E) log V)
Aplicação: GPS, redes de computadores
f(n) = g(n) + h(n). Usa heurística para guiar a busca.
Completo e Ótimo (com heurística admissível)
Aplicação: Jogos (pathfinding), robótica
Expande o nó com menor h(n). NÃO garante caminho mais curto
Complexidade: O(b^d)
Aplicação: Busca rápida, qualidade não prioritária
Generalização da BFS para grafos com pesos. Expande o nó com menor g(n).
Complexidade: O(b^(1+⌊C*/ε⌋))
F(n) = F(n-1) + F(n-2)
Sem PD: O(2ⁿ) | Com PD: O(n)
Exemplo clássico de memoização.
dp[i] = min(dp[i - coin] + 1)
Complexidade: O(n × m)
Encontra o número mínimo de moedas.
dp[i][w] = max(dp[i-1][w], valor[i] + dp[i-1][w - peso[i]])
Complexidade: O(n × W)
dp[i][j] = dp[i-1][j-1] + 1 se X[i]==Y[j], senão max(dp[i-1][j], dp[i][j-1])
Aplicação: Comparação de DNA, diff de arquivos
dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+custo)
Aplicação: Corretores ortográficos, plágio
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
Aplicação: Robótica, navegação
Escolhe sempre a maior moeda que cabe no troco.
✅ Ótimo para moedas canónicas (Euro: 1,2,5,10,20,50)
❌ Falha para moedas [1,6,10] com troco 13
Algoritmo de otimização local. Em cada passo, move-se na direção que aumenta o valor.
⚠️ Pode ficar preso em máximos locais
Estrutura: Fila (Queue)
Característica: Explora por níveis
Completo: ✅ | Ótimo: ✅ (arestas com peso 1)
Estrutura: Pilha (Stack)
Característica: Explora até o fim
Completo: ❌ | Ótimo: ❌
Estrutura: Fila de Prioridade (min-heap)
Característica: Considera custos
Completo: ✅ | Ótimo: ✅
Fórmula: f(n) = g(n) + h(n)
Característica: Usa heurística
Completo: ✅ | Ótimo: ✅ (com h admissível)
Complexidade: O(n) tempo, O(h) espaço
Fator de balanceamento = altura(esq) - altura(dir) ∈ {-1, 0, 1}
Rotações: LL, RR, LR, RL
Complexidade: O(log n) para inserção/remoção/busca
Usadas em TreeMap (Java), std::map (C++)
Propriedades de coloração garantem balanceamento
Árvore quase completa implementada em array.
Pai de arr[i] = arr[⌊(i-1)/2⌋] | Filhos = arr[2i+1], arr[2i+2]
Resolve problemas de Programação Linear.
Forma padrão: Maximizar Z = cᵀx sujeito a Ax ≤ b, x ≥ 0
Complexidade: O(2ⁿ) pior caso, O(n³) médio
Aplicação: Planeamento de produção, logística, alocação de recursos
Northwest Corner, Vogel, MODI
Minimizam custo de distribuição de produtos
Kruskal: O(E log E) | Prim: O(E log V)
Aplicação: Redes de telecomunicações, estradas
Ford-Fulkerson: O(E·f) | Edmonds-Karp: O(V·E²)
Aplicação: Redes de água, tráfego, internet
Algoritmo de decisão para jogos de dois jogadores (soma zero).
MAX: maximiza valor | MIN: minimiza valor
Complexidade: O(b^d)
Aplicação: Jogo da Velha, Xadrez, Damas
Otimização que elimina ramos desnecessários.
Complexidade: O(b^(d/2)) no melhor caso
Benefício: Reduz drasticamente o número de nós avaliados
Encontra raízes de funções reais.
Convergência: Quadrática (número de dígitos corretos dobra)
Aplicação: Engenharia, física, finanças
Sistema de EDOs para dinâmica predador-presa.
Método de Heun: Runge-Kutta 2ª ordem
Cada slot contém uma lista. Inserção O(1), busca O(λ).
Custo médio: ≈ λ/2 para busca com sucesso
Linear Probing: O(1 + 1/(1-λ)²)
Double Hashing: O(1/(1-λ))
⚠️ Performance degrada quando λ → 1
| Estrutura | Busca | Inserção | Remoção | Observação |
|---|---|---|---|---|
| Lista não ordenada | O(n) | O(1) | O(n) | — |
| Lista ordenada (array) | O(log n) | O(n) | O(n) | Busca binária |
| BST (não balanceada) | O(n) pior | O(n) pior | O(n) pior | Degenera para lista |
| AVL / Red-Black | O(log n) | O(log n) | O(log n) | Balanceada |
| Hash Table (chaining) | O(1) médio | O(1) médio | O(1) médio | λ constante |
| Hash Table (open addressing) | O(1/(1-λ)) médio | O(1/(1-λ)) médio | O(1/(1-λ)) médio | Clustering |
| Heap Binário | — | O(log n) | O(log n) | Extrai máximo |
| Fila (Queue) | — | O(1) | O(1) | FIFO |
| Pilha (Stack) | — | O(1) | O(1) | LIFO |