Algoritmos Minicurso

Minicurso de
Análise de Algoritmos http://www.ime.usp.br/~pf/livrinho-AA/ Paulo Feofiloff
Departamento de Ciência da Computação
Instituto de Matemática e Estatística
Universidade de São Paulo
27 de outubro de 2011

2

FEOFILOFF

Sumário
1

2

3

4

5

Introdução

9

1.1

Problemas e instâncias . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.2

Consumo de tempo de algoritmos . . . . . . . . . . . . . . . . . . . . 10

1.3

Recursão e algoritmos recursivos . . . . . . . . . . . . . . . . . . . . . 11

1.4

Convenções de notação . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

Comparação assintótica de funções

13

2.1

Notação O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2

Notação Ômega . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.3

Notação Teta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.4

Consumo de tempo de algoritmos . . . . . . . . . . . . . . . . . . . . 15

Solução de recorrências

17

3.1

Exemplo 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.2

Exemplo 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.3

Exemplo 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.4

Exemplo 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.5

Teorema mestre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Ordenação de vetor

25

4.1

Algoritmo Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.2

Divisão e conquista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

Segmento de soma máxima

27

5.1

O problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

5.2

Primeiro algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

5.3

Segundo algoritmo: divisão e conquista . . . . . . . . . . . . . . . . . 29

5.4

Terceiro algoritmo: programação dinâmica . . . . . . . . . . . . . .