An Lise Amortizada Contador Bin Rio
1239 palavras
5 páginas
Análise amortizadaCLRS 17
Algoritmos – p. 1
Análise amortizada
Serve para analisar uma sequência de operações ou iterações onde o pior caso individual não reflete o pior caso da sequência.
Em outras palavras, serve para melhorar análises de pior caso que baseiem-se diretamente no pior caso de uma operação/iteração e que deem uma delimitação frouxa para o tempo de pior caso da sequência.
Métodos:
agregado por créditos potencial Algoritmos – p. 2
Odômetro binário
Considere um contador binário, inicialmente zerado, representado em um vetor A[0 . . n − 1], onde cada A[i] vale
0 ou 1.
Operação: incrementa.
I NCREMENTA (A, n)
1
2
3
4
5
6
i←0 enquanto i < n e A[i] = 1 faça
A[i] ← 0 i←i+1 se i < n então A[i] ← 1
Consumo de tempo no pior caso: Θ(n)
Algoritmos – p. 3
Odômetro binário
Considere um contador binário, inicialmente zerado, representado em um vetor A[0 . . n − 1], onde cada A[i] vale
0 ou 1.
Operação: I NCREMENTA.
Consumo de tempo no pior caso: Θ(n).
O odômetro dá uma volta completa a cada 2n execuções do I NCREMENTA.
Quanto tempo leva para o odômetro dar uma volta completa? Leva O(n2n ).
Será que é Θ(n2n )?
Algoritmos – p. 4
Odômetro binário i 3
2
1
0
0
0
0
0
0
1
0
0
0
1
2
0
0
1
0
3
0
0
1
1
4
0
1
0
0
5
0
1
0
1
6
0
1
1
0
7
0
1
1
1
8
1
0
0
0
9
1
0
0
1
10
1
0
1
0
11
1
0
1
1
12
1
1
0
0
13
1
1
0
1
14
1
1
1
0
15
1
1
1
1
16
0
0
0
0
Algoritmos – p. 5
Odômetro binário i 3
2
1
0
0
0
0
0
0
1
0
0
0
1
2
0
0
1
0
3
0
0
1
1
4
0
1
0
0
5
0
1
0
1
6
0
1
1
0
7
0
1
1
1
8
1
0
0
0
9
1
0
0
1
10
1
0
1
0
11
1
0
1
1
12
1
1
0
0
13
1
1
0
1
14
1
1
1
0
15
1
1
1
1
16
0
0
0
0
Algoritmos – p. 6
Método agregado
Custo da volta completa é proporcional ao número de vezes que os bits são alterados. bit 0 muda 2n vezes bit 1 muda 2n−1 vezes bit 2 muda 2n−2 vezes
···
bit n − 2 muda 4 vezes bit n − 1 muda 2