Aula 04 Analise De Algoritmos Parte 1 V2

Introdução

Análise de Algoritmos

Conclusão

BCC202 - Estrutura de Dados I
Aula 04: Análise de Algoritmos (Parte 1)

Reinaldo Fortes
Universidade Federal de Ouro Preto, UFOP
Departamento de Ciência da Computação, DECOM
Website: www.decom.ufop.br/reifortes
Email: [e-mail]
Material elaborado com base nos slides do Prof. Túlio Toffolo (curso de 2013/01).

2013/02

Exercícios

Introdução

Análise de Algoritmos

Conclusão

Exercícios

Conteúdo

1

Introdução

2

Análise de Algoritmos
Análise de Algoritmos
Custo de um algoritmo
Função de complexidade
Tamanho da entrada de dados
Melhor Caso, Pior Caso e Caso Médio

3

Conclusão

4

Exercícios

BCC202 - Estrutura de Dados I

Aula 04: Análise de Algoritmos (Parte 1)

(2)

Introdução

Análise de Algoritmos

Conclusão

Exercícios

Conteúdo

1

Introdução

2

Análise de Algoritmos
Análise de Algoritmos
Custo de um algoritmo
Função de complexidade
Tamanho da entrada de dados
Melhor Caso, Pior Caso e Caso Médio

3

Conclusão

4

Exercícios

BCC202 - Estrutura de Dados I

Aula 04: Análise de Algoritmos (Parte 1)

(3)

Introdução

Análise de Algoritmos

Conclusão

Exercícios

Introdução

Análise de Algoritmos

Analisar um algoritmo consiste em “verificar” o custo do algoritmo em relação ao:
Tempo gasto para executá-lo.
Espaço (memória) ocupado em sua execução.

Esta análise é necessária para que se possa escolher o algoritmo mais adequado para resolver um dado problema.
É essencialmente importante em áreas de pesquisa operacional, otimização, teoria dos grafos, estatística, probabilidades, entre outras.

BCC202 - Estrutura de Dados I

Aula 04: Análise de Algoritmos (Parte 1)

(4)

Introdução

Análise de Algoritmos

Conclusão

Exercícios

Introdução

Cálculo do custo real pela execução do algoritmo

Medidas são inadequadas e o resultado não pode ser generalizado. Tais medidas são dependentes do compilador, que pode favorecer algumas construções em detrimento de outras.
Resultados dependem do hardware.
Quando