Complexidade

5. Análise de Complexidade de Algoritmos

João Pascoal Faria (versão original)
Ana Paula Rocha (versão 2003/2004)
Luís Paulo Reis (versão 2005/2006)

FEUP - MIEEC – Prog 2 - 2006/2007

Introdução
• Algoritmo: conjunto claramente especificado de instruções a seguir para resolver um problema
• Análise de algoritmos:
– provar que um algoritmo está correcto
– determinar recursos exigidos por um algoritmo (tempo, espaço, etc.)
• comparar os recursos exigidos por diferentes algoritmos que resolvem o mesmo problema (um algoritmo mais eficiente exige menos recursos para resolver o mesmo problema)
• prever o crescimento dos recursos exigidos por um algoritmo à medida que o tamanho dos dados de entrada cresce

2

1

Complexidade Espacial e Temporal
• Complexidade espacial de um programa ou algoritmo: espaço de memória que necessita para executar até ao fim S(n) - espaço de memória exigido em função do tamanho (n) da entrada

• Complexidade temporal de um programa ou algoritmo: tempo que demora a executar (tempo de execução)
T(n) - tempo de execução em função do tamanho (n) da entrada

• Complexidade ↑ versus Eficiência ↓
• Por vezes estima-se a complexidade para:
– o "melhor caso" (pouco útil)
– o "pior caso" (mais útil)
– o "caso médio" (igualmente útil)
3

Notação de O grande
• Na prática, é difícil (senão impossível) prever com rigor o tempo de execução de um algoritmo ou programa – Para obter o tempo a menos de:
• constantes multiplicativas (normalmente estas constantes são tempos de execução de operações atómicas)
• parcelas menos significativas para valores grandes de n

– Identificam-se as operações dominantes (mais frequentes ou muito mais demoradas) e determina-se o número de vezes que são executadas (e não o tempo de cada execução, que seria uma constante multiplicativa)
– Exprime-se o resultado com a notação de O grande
4

2

Notação de O grande
• Definição:
T(n) = O(f(n)) (ler: T(n) é de ordem f(n)) se e só se existem constantes positivas c e n0 tal que
T(n)≤