Considere um processo iterativo que consiste em uma sequência de n execuções de uma certa operação:
| _ para j crescendo de 1 até n faça |
| ____ Operação (E) |
A Operação é um algoritmo que atua sobre uma estrutura de dados E. Cada execução da Operação consome um tempo diferente, o que dificulta a estimativa precisa do consumo de tempo do processo todo. A análise amortizada procura fazer boas estimativas de consumo de tempo em situações como esta.
Esta página é inspirada no capítulo 17 de CLRS e na seção 4.6 de BB. Veja também seções 3.2.3 e 3.3 de MS. Veja ainda o verbete Amortized analysis na Wikipedia.
Considere uma sequência de n execuções de um certo algoritmo que atua sobre uma certa estrutura de dados. Cada execução do algoritmo tem um certo custo. (Troque custo por consumo de tempo se preferir.)
Suponha que o custo de cada execução do algoritmo depende das execuções anteriores. Suponha ainda que cada execução cara é precedida por muitas execuções baratas. Mais precisamente, suponha que existe c tal que, para todo m ≤ n, a soma dos custos das m primeiras execuções do algoritmo é cm. Então
tudo se passa como se cada execução tivesse custo c.
Dizemos que o custo amortizado de cada execução do algoritmo é c.
(O custo amortizado não deve ser confundido com custo médio. O conceito de custo amortizado se aplica a uma sequência de execuções de um algoritmo em que cada execução depende fortemente das anteriores. Já o custo médio é calculado sobre um conjunto ou universo de execuções independentes. Veja, por exemplo, o consumo médio do Quicksort.)
Um contador binário é um vetor de bits A[0..k−1]. O contador representa o número A[0]⋅20 + A[1]⋅21 + ⋅⋅⋅ + A[k−1]⋅2k−1.
| k−1 | 2 | 1 | 0 | |||||
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
O seguinte algoritmo soma 1 (em aritmética mod k) ao contador A:
| Operação ( ) |
| 1 _ i ← 0 |
| 2 _ enquanto i < k e A[i] = 1 faça |
| 3 ____ A[i] ← 0 |
| 4 ____ i ← i + 1 |
| 5 _ se i < k |
| 6 ____ então A[i] ← 1 |
(Estou tratando A e k são variáveis globais.) Suponha que o custo da Operação é igual ao número de "alterações de bits", ou seja, ao número de atribuições do tipo A[∗] ← ∗ (linhas 3 e 6). Cada execução da Operação altera 1 bit no melhor caso e k bits no pior.
Agora imagine uma sequência de n execuções da Operação, começando com o contador zerado:
| 11 _ para i crescendo de 0 até k−1 faça |
| 12 ____ A[i] ← 0 |
| 13 _ para j crescendo de 1 até n faça |
| 14 ____ Operação ( ) |
Qual o custo total da execução das linhas 13 a 14? No pior caso, cada execução da linha 14 produz k alterações de bits e portanto as n execuções da Operação têm custo nk no pior caso. Essa cota superior é correta mas exagerada, como veremos a seguir.
O bit A[0] é alterado em todas as execuções da Operação. O bit A[1] é alterado a cada duas execuções, ou seja, apenas ⌊n/2⌋ vezes (veja definição de piso). O bit A[2] é alterado apenas ⌊n/22⌋ vezes. O bit A[i] é alterado apenas ⌊n/2i⌋ vezes. Portanto, o custo total é menor que n + n/2 + n/22 + ⋅⋅⋅ + n/2i + ⋅⋅⋅ Esse número não passa de
2n.
Segue daí que o custo amortizado de cada execução da Operação não passa de 2.
É interessante refazer as contas usando uma metáfora contábil. Digamos que cada alteração de um bit custa uma moeda. Antes de cada execução da Operação, o contador possui um certo estoque de moedas (acumulado ao longo das iterações anteriores). Para dar início a uma execução da Operação, é preciso acrescentar duas moedas ao estoque. Durante a execução, as atribuição nas linhas 3 e 6 consomem parte do estoque deixando um saldo que, como veremos, nunca é negativo. (A ideia é que a primeira das duas moedas seja usada para custear a atribuição A[i] ← 1 na linha 6 e a segunda seja usada futuramente para custear a atribuição A[i] ← 0 na linha 3.) Graças a esse protocolo, temos o seguinte invariante:
antes de cada execução da Operação, o número de moedas em estoque é igual ao número de bits de A que têm valor 1.
Prova: É evidente que a propriedade vale antes da primeira execução da Operação. Suponha agora que ela vale antes de uma execução qualquer da Operação. Nesse momento, p bits menos significativos valem 1 e o p+1-ésimo bit vale 0. O invariante garante que temos pelo menos p moedas em estoque. Além disso, duas novas moedas são acrescentadas ao estoque. O bloco de linhas 2 a 4 da Operação consome p moedas do estoque para atribuir 0 aos p bits menos significativos. Depois, o p+1-ésimo bit assume valor 1 na linha 6 e assim consome uma das moedas novas. Assim, o número total de moedas em estoque continua igual ao número de bits 1 e a propriedade continua válida no fim desta execução da Operação. Isso encerra a prova.
O invariante mostra que o estoque de moedas é sempre suficiente para custear as alterações de bits na linha 3. Concluímos assim que a sequência de n execuções da Operação consome apenas
2n moedas.
Segue daí que as n execuções da Operação consomem Ο(n) unidades de tempo. Essa conclusão pode ser resumida dizendo que, no sentido amortizado, cada execução da Operação na linha 14 consome Ο(1) unidades de tempo, ou seja, uma quantidade de tempo que não depende de k nem de n.
O conceito de custo amortizado é útil para exprimir o consumo de tempo de muitos algoritmos. Eis alguns exemplos: