Considere uma sequência de n execuções de um algoritmo que atua sobre uma estrutura de dados. Suponha que cada execução do algoritmo consome um tempo diferente conforme o estado em que a estrutura de dados se encontra. Em outras palavras, o consumo de tempo de cada execução depende das execuções anteriores. Tipicamente, cada execução lenta é precedida por muitas execuções rápidas. A análise amortizada procura fazer estimativas de consumo de tempo em situações como esta.
No contexto deste capítulo, é conveniente usar a palavra operação como sinônimo de algoritmo. Da mesma forma, convém dizer custo da operação em vez de consumo de tempo do algoritmo.
Esta página é inspirada no capítulo 17 de CLRS.
Suponha que uma certa operação atua sobre uma estrutura de dados E e modifica a estrutura. Considere agora uma sequência de n execuções da operação:
| . para j := 1 até n faça |
| .ooo Operação (E) |
Cada execução da operação tem um certo custo, que depende do estado da estrutura E e portanto das execuções anteriores da operação.
Suponha que cada execução cara da operação é precedida por muitas execuções baratas. Mais precisamente, suponha que existe um número c tal que a soma dos custos das m primeiras execuções da operação não passa de c m. Então
tudo se passa como se cada execução tivesse custo ≤ c.
Dizemos que o custo amortizado (= amortized cost) de cada execução do operação não passa de 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 uma operação em que o custo de cada execução depende das execuções anteriores. Já o custo médio é calculado sobre um conjunto de execuções independentes. (Veja, por exemplo, o consumo esperado do Quicksort aleatorizado.)
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 |
A seguinte operação soma 1, em aritmética mod k, ao contador:
| Operação (A) |
| 1 . i := 0 |
| 2 . enquanto i < k e A[i] = 1 |
| 3 .ooo A[i] := 0 |
| 4 .ooo i := i + 1 |
| 5 . se i < k |
| 6 .ooo A[i] := 1 |
(Estou tratando k como variável global.)
Suponha que o custo da Operação
é igual ao número de alterações de bits
,
ou seja,
ao número de atribuições
A[i] := *
nas 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 := 0 até k−1 |
| 12 .ooo A[i] := 0 |
| 13 . para j := 1 até n |
| 14 .ooo Operação (A) |
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. 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 + ⋯ Essa soma não passa de
2n.
Segue daí que o custo amortizado de cada execução da Operação não passa de 2.
Metáfora contábil. É interessante refazer as contas usando uma metáfora contábil (= accounting method). 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 do processo iterativo: 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, CQD.
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.
Podemos dizer, um pouco mais vagamente, que o custo das n execuções da Operação é Ο(n). Essa conclusão pode ser resumida dizendo que, no sentido amortizado, cada execução da Operação na linha 14 tem custo Ο(1) , ou seja, um custo que não depende de k nem de n.
O conceito de custo amortizado é útil para exprimir o consumo de tempo de vários algoritmos: