Algoritmos

Cartões · 52

Algoritmo

Sequência finita e ordenada de instruções lógicas e bem definidas para resolver um problema ou executar uma tarefa computacional.

Complexidade Temporal

Mede a taxa de crescimento do tempo de execução de um algoritmo em função do tamanho da entrada; usada para prever e comparar desempenho.

Complexidade Espacial

Quantifica a quantidade de memória necessária para executar um algoritmo em relação ao tamanho da entrada; usada para otimizar recursos.

Notação Big-O

Representação matemática que descreve o limite superior assintótico (pior caso) do custo de tempo ou espaço de um algoritmo.

Busca Linear

Percorre elemento por elemento sequencialmente até encontrar o alvo ou atingir o fim da lista. Ideal para dados não ordenados ou pequenas listas.

Busca Binária

Divide iterativamente um vetor ordenado pela metade, comparando o valor central com o alvo. Usada para buscas rápidas em coleções já ordenadas.

Bubble Sort

Compara pares adjacentes repetidamente e os troca se estiverem fora de ordem, flutuando os maiores ao topo. Usado para fins didáticos.

Selection Sort

Encontra iterativamente o menor elemento da porção não ordenada e o move para o início. Usado quando o custo de trocas de memória deve ser mínimo.

Insertion Sort

Insere cada elemento na posição correta dentro de um subvetor já ordenado à esquerda. Muito eficiente para listas pequenas ou quase ordenadas.

Merge Sort

Divide recursivamente o vetor ao meio até subvetores unitários e os combina ordenadamente. Usado para ordenações estáveis com complexidade garantida O(n log n).

Quick Sort

Escolhe um pivô, particiona os dados entre menores e maiores que ele e ordena as partes recursivamente. Usado como padrão de alta performance geral.

Heap Sort

Transforma o vetor em uma árvore max-heap e extrai sucessivamente a raiz para o final. Usado para ordenar in-place com garantia de O(n log n).

Counting Sort

Conta a frequência de chaves distintas e calcula as posições diretas no vetor final sem comparações. Usado para inteiros em faixas pequenas conhecidas.

Radix Sort

Ordena números processando dígito por dígito, do menos significativo ao mais significativo, usando ordenação estável. Usado para inteiros ou textos.

Recursão

Técnica em que uma função chama a si mesma para resolver instâncias menores do mesmo problema, exigindo caso base. Usada em estruturas hierárquicas.

Divisão e Conquista

Paradigma que quebra o problema em subproblemas independentes, resolve-os recursivamente e junta as soluções. Usado em Merge Sort e multiplicação de Karatsuba.

Algoritmo Guloso (Greedy)

Faz a escolha localmente ótima a cada etapa na esperança de encontrar o ótimo global. Usado no algoritmo de Dijkstra e codificação de Huffman.

Programação Dinâmica

Resolve subproblemas sobrepostos armazenando seus resultados prévios (memoização ou tabulação) para evitar recomputações. Usado no problema da mochila.

Backtracking

Explora caminhos de solução passo a passo e retrocede ao encontrar um beco sem saída ou violar restrições. Usado em quebra-cabeças como N-Rainhas e Sudoku.

Busca em Largura (BFS)

Explora vértices de um grafo nível a nível usando uma fila (FIFO). Usada para encontrar o caminho mais curto em grafos não ponderados.

Busca em Profundidade (DFS)

Explora o grafo avançando o máximo possível ao longo de cada ramo antes de retroceder, usando pilha ou recursão. Usada para detectar ciclos e ordenação topológica.

Algoritmo de Dijkstra

Calcula o menor caminho a partir de uma origem única usando fila de prioridade, expandindo sempre o nó de menor custo. Usado em roteamento de redes e mapas sem pesos negativos.

Algoritmo de Bellman-Ford

Relaxa todas as arestas V-1 vezes para encontrar caminhos mínimos de origem única. Usado para detectar ciclos negativos em grafos com pesos negativos.

Algoritmo de Floyd-Warshall

Compara todos os pares de vértices via programação dinâmica para achar caminhos mais curtos entre todos os pares. Usado em análise de redes densas.

Algoritmo de Kruskal

Ordena todas as arestas por peso e as adiciona evitando ciclos através de conjuntos disjuntos (Union-Find). Usado para construir Árvores Geradoras Mínimas.

Algoritmo de Prim

Cresce a árvore geradora mínima nó a nó, conectando sempre a aresta de menor peso a um vértice não visitado. Usado para Árvores Geradoras Mínimas em grafos densos.

Algoritmo A* (A-Estrela)

Busca heurística que combina o custo real acumulado com a estimativa heurística até o objetivo. Usado para navegação e pathfinding em jogos.

Ordenação Topológica

Gera uma sequência linear de vértices de um dígrafo acíclico (DAG) onde cada nó precede seus dependentes. Usada para resolver ordens de dependência e compilação.

Algoritmo de Kahn

Encontra a ordenação topológica de um DAG removendo iterativamente nós que possuem grau de entrada zero. Usado em agendamento de tarefas com dependências.

Tabela Hash (Hashing)

Mapeia chaves para índices de um vetor por meio de uma função matemática, permitindo acesso quase imediato. Usada para implementar dicionários e caches rápidos.

Tratamento de Colisão por Encadeamento

Armazena elementos colididos na mesma posição da tabela hash inserindo-os em uma lista encadeada vinculada àquele índice. Usado para manter integridade da hash.

Endereçamento Aberto

Procura a próxima posição livre no próprio vetor da tabela hash caso o índice original esteja ocupado. Usado para economizar alocações de nós externos.

Árvore Binária de Busca (BST)

Estrutura hierárquica onde filhos esquerdos são menores e direitos são maiores que o nó pai. Usada para buscas, inserções e remoções dinâmicas ordenadas.

Árvore AVL

Árvore binária auto-balanceada que realiza rotações se a diferença de altura entre subárvores ultrapassar um. Usada para garantir busca O(log n) constante.

Árvore Rubro-Negra

Árvore auto-balanceada guiada por regras de coloração de nós que limitam desequilíbrios. Usada internamente em mapas e conjuntos da maioria das linguagens.

Árvore de Segmentos (Segment Tree)

Árvore que armazena agregações de intervalos em nós pais para responder consultas e atualizações em O(log n). Usada em problemas de consulta de faixa (Range Queries).

Trie (Árvore de Prefixos)

Árvore n-ária onde cada nó representa um caractere e caminhos formam palavras completas. Usada em sistemas de autocompletar e corretores ortográficos.

Algoritmo KMP (Knuth-Morris-Pratt)

Busca padrões em texto usando uma tabela de prefixos pré-computada para evitar comparações redundantes ao retroceder. Usado em buscas em strings longas.

Algoritmo de Rabin-Karp

Compara valores de hashes calculados sequencialmente (rolling hash) entre o padrão e janelas do texto. Usado para busca de múltiplos padrões e detecção de plágio.

Codificação de Huffman

Gera códigos binários de tamanho variável com base na frequência dos símbolos usando árvore binária gulosa. Usada na compressão de dados como ZIP e JPEG.

Algoritmo de Ford-Fulkerson

Calcula o fluxo máximo em uma rede encontrando caminhos aumentantes repetidamente até a saturação. Usado no dimensionamento de tráfego e logística.

Algoritmo de Edmonds-Karp

Implementação do fluxo máximo de Ford-Fulkerson usando BFS para priorizar caminhos aumentantes mais curtos. Usado para evitar loops infinitos em redes de fluxo.

Algoritmo Minimax

Avalia árvores de decisão simulando as escolhas do jogador adversário para maximizar o ganho próprio e minimizar o alheio. Usado em IA para jogos de tabuleiro.

Poda Alfa-Beta

Elimina ramos do algoritmo Minimax que comprovadamente não afetarão a decisão final do jogador. Usada para acelerar mecanismos de IA de xadrez.

Algoritmo de Euclides

Calcula o Máximo Divisor Comum (MDC) substituindo repetidamente o maior número pelo resto de sua divisão pelo menor. Usado em criptografia e teoria dos números.

Crivo de Eratóstenes

Identifica números primos até certo limite marcando iterativamente os múltiplos de cada número primo encontrado. Usado para geração eficiente de primos.

Exponenciação Modular Rápida

Calcula potências elevadas sob módulo reduzindo a base ao quadrado iterativamente a cada bit do expoente. Usada como base de algoritmos como RSA.

Union-Find (Disjoint Set)

Estrutura que rastreia elementos divididos em subconjuntos disjuntos com operações quase instantâneas de união e busca. Usada no algoritmo de Kruskal.

Algoritmo de Tarjan

Usa uma única passagem de DFS para identificar todos os componentes fortemente conexos em um grafo direcionado. Usado para particionamento e análise de redes.

Dois Ponteiros (Two Pointers)

Varre coleções usando dois índices móveis que convergem, divergem ou correm na mesma velocidade. Usado para encontrar pares com soma alvo em listas ordenadas.

Janela Deslizante (Sliding Window)

Mantém um subintervalo contínuo móvel com tamanho fixo ou variável ao longo de um vetor. Usada para computar médias móveis e subsequências ideais.

Problema P vs NP

Questão central que indaga se problemas cujas soluções podem ser verificadas rapidamente (NP) também podem ser resolvidos rapidamente (P).