Algoritmo

Análise de Algoritmos
2008

Aula 1: Introdução

Paulo Feofiloff
IME, Universidade de São Paulo

1

2

O que é AA? Um exemplo

CLRS: Cormen, Leiserson, Rivest, Stein
• “Having a solid base of algorithmic knowledge and technique is one characteristic that separates the truly skilled programmers from the novices.
With modern computing technology, you can accomplish some tasks without knowing much about algorithms, but with a good background in algorithms, you can do much, much more.”

Problema: Rearranjar um vetor em ordem crescente
A[1 . . n] é crescente se A[1] ≤ · · · ≤ A[n]

22 33 33 33 44 55 11 99 22 55 77
• “Uma base sólida de conhecimento e técnica de algoritmos é uma das características que separa o programador experiente do aprendiz.
Com a moderna tecnologia de computação, você pode realizar algumas tarefas sem saber muito sobre algoritmos, mas com um boa base em algoritmos você pode fazer muito, muito mais.”
3

11 22 22 33 33 33 44 55 55 77 99

4

Algoritmo: Rearranja A[1 . . n] em ordem crescente

Análise da correção: O algoritmo faz o que prometeu?

ORDENA-POR-INSERÇÃO (A, n)
1
2
3
4
5
6
7

• Invariante: no início de cada iteração, A[1 . . j −1] é crescente

para j ← 2 até n faça chave ← A[j ] i←j−1 enquanto i ≥ 1 e A[i] > chave faça
A[i + 1] ← A[i] i←i−1 A[i + 1] ← chave

• Se vale na última iteração, o algoritmo está correto!

1 j n
22 33 33 33 44 55 11 99 22 55 77

Note a documentação
6

5

ORDENA-POR-INSERÇÃO (A, n)
1
2
3
4
5
6
7

Análise do desempenho: Quanto tempo consome?

para j ← 2 até (*) n faça chave ← A[j ] i←j−1 enquanto i ≥ 1 e A[i] > chave faça
A[i + 1] ← A[i] i←i−1 A[i + 1] ← chave

• Regra de três
• Regra de três não funciona!
• Suponha 1 unidade de tempo por linha

linha
1
2
3
4
5
6
7

1 j n
22 33 33 33 44 55 11 99 22 55 77

total de unidades de tempo
=n
= n−1
= n−1
≤ 2 + 3 + ··· + n
= (n − 1)(n + 2)/2
≤ 1 + 2 + · · · +