Complexidade Assintótica

Prévia do material em texto

Monitoria de Algoritmos
Complexidade Assintótica2
“
A ideia principal da análise assintótica é 
ter uma medida de eficiência de um 
algoritmo que não dependa de 
constantes específicas de uma máquina 
e não exija que o algoritmo seja 
implementado e executado por um 
programa, a fim ser comparado. As 
notações assintóticas são ferramentas 
matemáticas que permitem representar 
a complexidade do tempo de algoritmos, 
relativos a sua entrada.
Ω
◇ Lower Bound
◇ Melhor caso
◇ Tempo em relação ao 
tamanho da entrada
◇ Suprime constantes 
multiplicativas
◇ Suprime termos de 
menor ordem
Θ
◇ Define comportamento 
assintótico exato de um 
algoritmo
◇ Tempo em relação ao 
tamanho da entrada
◇ Suprime constantes 
multiplicativas
◇ Suprime termos de 
menor ordem
Big O
◇ Upper Bound
◇ Pior caso
◇ Tempo em relação ao 
tamanho da entrada
◇ Suprime constantes 
multiplicativas
◇ Suprime termos de 
menor ordem
Tempo Relativo à Entrada
Tempo Relativo à Entrada
Tempo Relativo à Entrada