Lista encadeada
5584 palavras
23 páginas
Análise de algoritmos•
Algoritmos e Estruturas de Dados II
Aulas 05 e 06
•
•
•
Analisar a complexidade computacional de um algoritmo significa prever os recursos de que o mesmo necessitará:
− Memória
− Largura de banda de comunicação
− Hardware
− Tempo de execução
Geralmente existe mais de um algoritmo para resolver um problema A análise de complexidade computacional é fundamental no processo de definição de algoritmos mais eficientes para a sua solução
Em geral, o tempo de execução cresce com o tamanho da entrada 2º Semestre de 2011
2
Porque estudar análise de algoritmos?
•
Porque estudar análise de algoritmos?
O tempo de computação e o espaço na memória são recursos limitados
− Os computadores podem ser rápidos, mas não são infinitamente
•
rápidos
•
•
− A memória pode ser de baixo custo, mas é finita e não é gratuita
Os recursos devem ser usados de forma sensata, e algoritmos eficientes em termos de tempo e espaço devem ser projetados
Com o aumento da velocidade dos computadores, torna-se cada vez mais importante desenvolver algoritmos mais eficientes, devido ao aumento constante do tamanho dos problemas a serem resolvidos
Suponha que para resolver um determinado problema você tem disponível um algoritmo exponencial (2n) e um computador capaz de executar 104 operações por segundo
2n na m áquina 104 tem (s) po tam anho 0,10
10
1
13
1m inuto 60
19
1 hora
3.600
25
1 dia
86.400
30
1 ano 31.536.000
38
3
4
Porque estudar análise de algoritmos?
•
Porque estudar análise de algoritmos?
•
Compra de um novo computador capaz de executar 109 operações por segundo
tem (s) po 0,10
1
1m inuto 60
1 hora
3.600
1 dia
86.400
1 ano 31.536.000
2n na m áquina 104 2n na m áquina 109 tam anho tam anho
10
27
13
30
19
36
25
42
30
46
38
55
Investir em algoritmo:
− Você encontrou um algoritmo quadrático (n2) para resolver o problema
tem (s)