Algoritmo da mochila

ANÁLISE DE ALGORITMOS
Paulo Feofiloff
Instituto de Matemática e Estatística Universidade de São Paulo

agosto 2009

Introdução

P. Feofiloff (IME-USP)

Análise de Algoritmos

agosto 2009

2 / 102

Introdução

Um exemplo

Problema Encontrar a soma dos elementos positivos de um vetor A[1 . . n] Uma instância do problema: Encontrar a soma dos elementos positivos do vetor (20, −30, 15, −10, 30, −20, −30, 30)
1 20 n=8 30

−30

15

−10

30

−20 −30

P. Feofiloff (IME-USP)

Análise de Algoritmos

agosto 2009

3 / 102

Introdução

Um exemplo

Algoritmo SOMAPOSITIVOS (A, n) 1 s←0 2 para i ← 1 até n faça 3 se A[i] > 0 4 então s ← s + A[i] 5 devolva s

P. Feofiloff (IME-USP)

Análise de Algoritmos

agosto 2009

4 / 102

Introdução

Um exemplo

O algoritmo está correto? testes só podem mostrar que o algoritmo está errado análise pode provar que o algoritmo está correto O algoritmo está correto Invariante: no começo de cada iteração s é a soma dos positivos de A[1 . . i−1] No fim, s é a soma dos positivos de A[1 . . n]

P. Feofiloff (IME-USP)

Análise de Algoritmos

agosto 2009

5 / 102

Introdução

Um exemplo

Quanto tempo consome a execução do algoritmo? depende da instância Consumo de tempo do algoritmo proporcional ao número de iterações tempo de cada iteração não depende de n tempo total: proporcional a n se n dobra, o tempo dobra se n decuplica, o tempo decuplica

P. Feofiloff (IME-USP)

Análise de Algoritmos

agosto 2009

6 / 102

Introdução

Um exemplo

Observações sobre consumo de tempo: estimar consumo do algoritmo, independente do computador despreze constantes multiplicativas: 10 n é o mesmo que n consumo de tempo é diferente para cada instância do problema agrupe instâncias por “tamanho” o conceito de tamanho de uma instância muitas instâncias têm o mesmo tamanho consumo de tempo no pior caso consumo de tempo no melhor caso

P. Feofiloff (IME-USP)

Análise de Algoritmos

agosto