3 ComplexidadeDeAlgoritmos

Complexidade de Algoritmos
ACH2002 - Introdução à Ciência da Computação II

Delano M. Beder
Escola de Artes, Ciências e Humanidades (EACH)
Universidade de São Paulo [e-mail] 08/2008

Material baseado em slides do professor Marcos Chaim

Delano M. Beder (EACH - USP)

Complexidade de Algoritmos

ACH2002

1/1

Projeto de Algoritmos

Algoritmos são projetados para resolver problemas
Problema: encontrar a melhor rota, em termos de tempo de entrega, dos produtos das Casas Ceará em Ermelino Matarazzo
Solução: algoritmo para descoberta da melhor rota tendo como entrada os locais de entrega
Projetar algoritmos implica estudar o seu comportamento
No tempo: quanto tempo vai demorar para encontrar a solução do problema No espaço: quanto de memória será necessário para encontrar a solução Delano M. Beder (EACH - USP)

Complexidade de Algoritmos

ACH2002

2/1

Análise de algoritmos

Na área de análise de algoritmos há dois problemas distintos:
1

Análise de um algoritmo particular
Qual é o custo de usar um dado algoritmo para resolver um problema específico?
Quantas vezes cada parte desse algoritmo vai ser executada?
Quanto de memória será necessária?

Delano M. Beder (EACH - USP)

Complexidade de Algoritmos

ACH2002

3/1

Análise de algoritmos
2

Análise de uma classe de algoritmos
Qual é o algoritmo de menor custo possível para resolver um problema específico?
Isto implica investigar toda uma família de algoritmos
Para realizar esta investigação limites podem ser impostos:
Exemplo: número mínimo de comparações necessárias para ordenar n números por meio de comparações sucessivas.
Logo, nenhum algoritmo vai fazer melhor que isto ⇒ menor custo possível. Menor custo possível ⇒ medida de dificuldade.

Se o custo do algoritmo A = menor custo possível ⇒ A é ótimo.
Delano M. Beder (EACH - USP)

Complexidade de Algoritmos

ACH2002

4/1

Complexidade
Como medir o custo de um algoritmo?
Como comparar o custo de vários algoritmos que resolvem um problema? 1

Medição direta do