Mapa Mental - Algoritmos e Complexidade

Prévia do material em texto

Recursividade Árvores Binárias e AVL Recursão do fatorial é Árvore AVL é autobalanceada com um exemplo clássico de diferença máxima de altura 1 recursividade simples Árvores AVL mantêm altura Recursividade linear balanceada para otimizar buscas divide problema em Árvore binária desbalanceada subproblemas menores aumenta a complexidade de busca Recursividade múltipla Cada nó em árvore binária pode envolve chamadas ter até dois descendentes recursivas mais complexas Recursão de cauda permite otimizações pelo compilador Algoritmos Algoritmos de Ordenação Análise de Algoritmos e Selection Sort divide array em Complexidade assintótica parte ordenada e não ordenada expressa comportamento para Selection Sort é ineficiente para Complexidade entradas grandes grandes conjuntos de dados Tipos de dados heterogêneos têm Insertion Sort é eficiente quando elementos em posições a lista está quase ordenada adjacentes Quick Sort e Merge Sort têm Complexidades corretas são complexidade O(n log n) essenciais para avaliar eficiência real Funções indicam limites superiores do tempo de execução Complexidade e Eficiência Algoritmos eficientes são essenciais para grandes volumes de dados Algoritmos em Grafos Balanceamento em árvores reduz tempo de busca para O(log n) Tipos de Dados Busca em profundidade (DFS) explora vértices recursivamente Algoritmos com complexidade O(n Registros armazenam dados log n) são considerados eficientes heterogêneos em posições DFS marca vértices alcançáveis Algoritmos ineficientes aumentam de memória adjacentes a partir de um vértice inicial custo computacional e tempo Tipos elementares são Busca em largura (BFS) explora homogêneos e ocupam grafos em camadas, diferente do espaço fixo DFS Tipos estruturados Algoritmos de grafos são agrupam múltiplos essenciais para análise de elementos em uma única conexões estrutura Organização dos dados impacta eficiência de acesso e manipulação