Please enable JavaScript.
Coggle requires JavaScript to display documents.
Análise de Eficiência de Algoritmos - Coggle Diagram
Análise de Eficiência de Algoritmos
Quesitos Fundamentais
tempo de execução
Absoluto T(n)
Relativo C(n)
Em termos de uma operação básica op que leva c para ser executada em um computador particular.
T(n) = c * C(n), aproximadamente
A análise pode ser feita em diferentes situações: Pior caso, caso Médio e Melhor caso. Pode também ser feita em funções recursivas ou não recursivas.
Geralmente encontrar a complexidade para o caso médio é mais trabalhoso. Para alguns algoritmos, C(n) no caso médio é melhor do que C(n) no pior caso
Consiste em dividir todas as instâncias em várias classes, de modo que o número de vezes que a operação básica é executada em cada instância de classe é o mesmo, e assumir uma determinada distribuição de probabilidades das entradas.
A maneira de determinar a eficiência de pior caso de um algoritmo consiste em analisar para ver que tipo de entrada produz a maior quantidade de execuções da operação básica entre todas as entradas possíveis de tamanho n.
Para obter o melhor caso, determinamos os tipos de entradas para as quais C(n) será o menor entre todas as entradas possíveis de tamanho n. (Observe que o melhor
caso não significa a menor entrada; significa a entrada de tamanho n para a qual o algoritmo é executado mais rapidamente.)
Análise amortizada
Executar o algoritmo várias vezes com diferentes eficiências
espaço de memória
Notação Assintótica
O(g(n)): Funções com ordem de grandeza que não é pior do que g(n)
Ω(g(n)): Funções de ordem de grandeza que não é melhor do que g(n)
Θ(n): Funções de ordem de grandeza similar a de g(n)
Algumas classes Básicas de Eficiência:
1
log(n)
n log(n)
n
n²
2^n
n!
Como o conceito de limite do cálculo infinitesimal pode ajudar na análise asíntótica?
Calculamos o limite quando n -> ∞ de t(n)/g(n)
Se lim = 0, a ordem de t(n) é menor que a de g(n)
Se lim = c (constante), a ordem de t(n) é igual
Se lim = ∞, a ordem é maior