Aula 02 ANLISE DE ALGORITMO AnaliseComplexidade parte01

Análise de Algoritmos
Professor: Thiago de Medeiros Gualberto

Análise de Desempenho

Análise de Desempenho
É necessário ver se o código está correto e fazer análise de desempenho Correto – Funciona?
Análise – Quanto tempo demora? Quanto de memória usa? É eficiente? Como analisar o tempo?
Empiricamente (marcar no relógio)
Depende do computador, usuário da rede, linguagem, ...
Analiticamente.

do compilador, da

Análise de Desempenho
É realmente necessário medir tempo?
Problema do Caixeiro Viajante
Determinar a menor rota para percorrer uma série de cidades.
Como descobrir a melhor rota?
Testar todas, calcular cada uma, escolher a menor.

O que acontece com 50 cidades? Quantas rotas possíveis?

Análise de Desempenho
Supondo um computador que calcule 1.000.000.000 de rotas por segundo.
6 x 1053 segundos
1,92 x 1044 séculos

E se inventassem um computador 1.000.000x mais rápido? Levaria 1,92 x 1038 séculos

Medida do Tempo de Execução de um
Programa
O projeto de algoritmos é fortemente influenciado pelo estudo de seus comportamentos.
Depois que um problema é analisado e decisões de projeto são finalizadas, é necessário estudar as várias opções de algoritmos a serem utilizados, considerando os aspectos de tempo de execução e espaço ocupado.
Muitos desses algoritmos são encontrados em áreas como pesquisa operacional, otimização, teoria dos grafos, estatística, probabilidades, entre outras.

Tipos de Problemas na Análise de
Algoritmos
Análise de um algoritmo particular.
Qual é o custo de usar um dado algoritmo para resolver um problema específico? Características que devem ser investigadas: análise do número de vezes que cada parte do algoritmo deve ser executada, estudo da quantidade de memória necessária.

Análise de uma classe de algoritmos.
Qual é o algoritmo de menor custo possível para resolver um problema particular? Toda uma família de algoritmos é investigada.
Procura-se identificar um que seja o melhor possível.
Coloca-se limites para a complexidade