Algoritmo

Disponível somente no TrabalhosFeitos
  • Páginas : 50 (12406 palavras )
  • Download(s) : 0
  • Publicado : 28 de agosto de 2012
Ler documento completo
Amostra do texto
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 taskswithout 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 modernatecnologia 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 decada 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 + · · · +(n−1) = n(n − 1)/2
≤ 1 + 2 + · · · + (n−1) = n(n − 1)/2
= n−1

3
7
total ≤ 2 n2 + 2 n − 4 unidades de tempo

• vale na primeira iteração
• se vale em uma iteração, vale na seguinte
7

8

3
• Algoritmo consome ≤ 2 n2 + 7 n − 4 unidades de tempo
2

Outra tática:
• número de comparações “ A[i] > chave ”

3
• 2 é pra valer?

1
1
≤ 2 + 3 + · · · + n = 2 (n − 1)(n + 2) ≤ 2 n2 +1 n − 1
2

Não, pois depende do computador

1
• 2 é pra valer?

• n2 é pra valer?

Não, pois depende do computador

Sim, pois só depende do algoritmo

• n2 é pra valer?
• Queremos um resultado que só dependa do algoritmo

Sim, pois só depende do algoritmo
• Queremos resultado que só dependa do algoritmo

10

9

• “ n2” é informação valiosa
• mostra evolução do tempo comn:

AA “in a nutshell”
n

n2

2n

4n2

10n

100n2

• Problema
• Instâncias do problema
• Tamanho de uma instância
• Algoritmo
• Análise da correção do algoritmo
• Análise do desempenho (velocidades) do algoritmo
• Desempenho em função do tamanho das instâncias
• Pior caso
• Evolução do consumo de tempo em função de n
• Independente do computador e da implementação

1112

Notação O: comparação assintótica de funções
• Comparação assintótica grosseira de funções f (n) e g (n)
• Qual das duas cresce mais rápido?
• Algo com sabor de f (n) “ ≤” g (n)

Aula 2

• Despreze valores pequenos de n:

n→∞

• Despreze constantes multiplicativas:

Notação O

• Despreze termos de ordem inferior:

100 n2 “ ≤” n2
n2 + 10n + 10 “ ≤” 2 n2

13

14Exemplo 1

f (n) e g (n) assintoticamente não-negativas
n2 + 10n = O(n2)

Definição: Dizemos que f = O(g ) se
existem constantes c > 0 e N > 0 tais que

Prova:

f (n) ≤ c · g (n) para todo n ≥ N

• se n ≥ 10 então n2 + 10n ≤ n2 + n · n = n2 + n2 = 2 · n2
• resumo: n2 + 10n ≤ 2 n2 para todo n ≥ 10

Em outras palavras: para todo n suficientemente grande,
f (n) é dominado por um múltiplo de...
tracking img