Please enable JavaScript.
Coggle requires JavaScript to display documents.
Eficiência de Algoritmos - Coggle Diagram
Eficiência de Algoritmos
Tipos de Eficiência
Tempo (Time Complexity)
Espaço (Space Complexity)
Tamanho da Entrada
Parâmetro de entrada: n
Ex: tamanho da lista, ordem da matriz
Casos especiais: número de bits (ex: primalidade)
Medida de Tempo
Evitar segundos ou milissegundos
Contar número de operações básicas
Ex: comparação, multiplicação
Estimativa de Tempo
Fórmula: T(n) ≈ cop × C(n)
Constantes ignoradas para n grande
Ordem de Crescimento
Crescimento assintótico
Tabela de ordens
log n
n
n log n
n²
n³
2ⁿ
n!
Casos de Eficiência
Pior caso (Worst-case)
Melhor caso (Best-case)
Caso médio (Average-case)
Eficiência amortizada (Amortized)
Notações Assintóticas
O(g(n)) — limite superior
Ω(g(n)) — limite inferior
Θ(g(n)) — limite exato
Limites e comparações
lim t(n)/g(n) = 0 → o(g(n))
lim t(n)/g(n) = c ≠ 0 → Θ(g(n))
lim t(n)/g(n) = ∞ → ω(g(n))
Classes de Eficiência
Constante: 1
Logarítmica: log n
Linear: n
Linearítmica: n log n
Quadrática: n²
Cúbica: n³
Exponencial: 2ⁿ
Fatorial: n!
Etapas da Análise (Algoritmos Não Recursivos)
Escolher métrica de tamanho da entrada
Identificar a operação básica
Verificar variações por entrada (casos diferentes)
Montar expressão ou somatório de repetições
Simplificar e determinar a ordem de crescimento
Exemplos
Busca sequencial
Melhor caso: Θ(1)
Pior caso: Θ(n)
Médio caso: Θ(n)
Encontrar máximo em vetor
Comparações: n−1 → Θ(n)
Verificar elementos distintos
Comparações: n(n−1)/2 → Θ(n²)
Multiplicação de matrizes
Θ(n³)
Conversão decimal para binário
Θ(log n)