Analise Complexidade

COMPLEXIDADE DE ALGORITMOS
Algoritmos
• Seqüência de instruções necessárias para a resolução de um problema bem formulado
• Permite implementação computacional

COMPLEXIDADE DE ALGORITMOS
• Um algoritmo resolve o problema quando para qualquer entrada produz uma resposta correta
• Mesmo resolvendo um problema, um algoritmo pode não ser aceitável na prática por requerer muito espaço e tempo
• Um problema é considerado INTRATÁVEL, se não existe um algoritmo para ele cuja demanda de recursos computacionais seja razoável.

1

COMPLEXIDADE DE ALGORITMOS
Questões
• O problema em questão é tratável?
• Existe um algoritmo que demande quantidade razoável de recursos computacionais? • Quais os custos deste algoritmo?
• Existe um algoritmo melhor?
• Como comparar algoritmos?

COMPLEXIDADE DE ALGORITMOS
Exercício:

1 ! + 2 ! + 3 ! + ... + n !

2

COMPLEXIDADE DE ALGORITMOS

Estas e outras questões são abordadas em uma área de conhecimento denominada
Análise de complexidade de algoritmos

COMPLEXIDADE DE ALGORITMOS
• O custo final de um algoritmo pode estar relacionado a diversos fatores:
- Tempo de execução
- Utilização de memória principal
- Utilização de disco
- Consumo de energia, etc...
• Medidas importantes em outros contextos:
- legibilidade do código
- custo de implementação
- portabilidade
- extensibilidade

3

COMPLEXIDADE DE ALGORITMOS
Exemplo:
Solução de um sistema de equações lineares
AX = 0
Métodos:
Cramer (determinantes)
Gauss (escalonamento)

COMPLEXIDADE DE ALGORITMOS
Estimativa empírica de tempo, para um processador rodando em 3GHz n Cramer
Gauss
2
4 ns
2 ns
3
12 ns
8 ns
4
48 ns
20 ns
5
240ns
40 ns
10
7.3ms
330 ns
20
152 anos
2.7 ms
Em maioria dos casos, complexidade em tempo é preocupação principal

4

COMPLEXIDADE DE ALGORITMOS
Outro exemplo
- Busca seqüencial
- Dado um vetor de números, verificar se um número chave encontra-se neste vetor char achou = 0; i = 0; while (!achou && i<n) { achou = (vet[i] == chave); i++; } if (achou) return(i);
else