Teorica AnaliseComplexidade

Análise de complexidade
Introdução
➔ Algoritmo: sequência de instruções necessárias para a resolução de um problema bem formulado (passíveis de implementação em computador) ➔ Estratégia:
– especificar (definir propriedades)
– arquitectura (algoritmo e estruturas de dados)
– análise de complexidade (tempo de execução e memória)
– implementar (numa linguagem de programação)
– testar (submeter entradas e verificar observância das propriedades especificadas) Análise de complexidade
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

Análise de complexidade
Análise de algoritmos
➔ Que dados usar ?
― dados reais: verdadeira medida do custo de execução
― dados aleatórios: assegura-nos que as experiências testam o algoritmo e não apenas os dados específicos
•

Caso médio

– dados perversos: mostram que o algoritmo funciona com qualquer tipo de dados
•

Pior caso!

― dados benéficos:
•

Melhor caso

Análise de complexidade
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 ↑ vs. Eficiência ↓
➔ Por vezes estima-se a complexidade para o “melhor caso” (pouco útil), o “pior caso” (mais útil) e o “caso médio” (igualmente útil)

Análise de complexidade
Complexidade temporal
➔ Análise precisa é uma tarefa complicada
― algoritmo é implementado numa dada linguagem
― a linguagem é