Uma tabela é dinâmica se que incha e encolhe, conforme a necessidade, ao longo da execução de um algoritmo. Esta página trata de algoritmos de manipulação de tabelas dinâmicas.
A página é inspirada na seção 17.4 de CLRS. Veja também seção 3.2 de MS. Veja ainda o verbete Dynamic array na Wikipedia.
Uma tabela dinâmica (= dynamic table = unbounded array) é uma vetor sujeito as expansões e contrações. Nossa tabela dinâmica reside num vetor A[1 .. m .. t]. Diremos que t é o tamanho e m é a carga da tabela. As m primeiras posições estão ocupados com dados relevantes e as demais estão livres. Se m = 0, diremos que a tabela está vazia. Se m = t, a tabela está cheia.
| 1 | m | t | |||||||||||||
11
| 22
| 33
| 44
| 55
| 66
| 77
| 88
| 99
|
|
|
|
|
|
|
| |
Os parâmetros A, t e m serão tratados como variáveis globais. A variável A é um ponteiro (que aponta para o primeiro elemento do vetor).
Considere inicialmente o comportamento da tabela sob a operação de inserção de novos objetos. A operação de inserção de um objeto a pode ser escrita assim:
| Insere-na-Tabela (a) |
| 11 _ se t = 0 |
| 12 ____ então A ← Aloca-Tabela (1) |
| 13 ____ então t ← 1 |
| 14 _ se m = t |
| 15 ____ então B ← Aloca-Tabela (2t) |
| 16 ____ então para k crescendo de 1 até m faça |
| 17 _______ então B[k] ← A[k] |
| 18 ____ então Libera-Tabela (A) |
| 19 ____ então A ← B |
| 10 ____ então t ← 2t |
| 11 _ m ← m + 1 |
| 12 _ A[m] ← a |
A linha 2 aloca uma nova tabela de tamanho 1. A linha 5 aloca uma nova tabela de tamanho 2t. As linhas 5 a 10 produzem uma expansão da tabela; a linha 7, em particular, realoca o elemento A[k]. Na linha 8, o espaço ocupado por A é liberado. Depois da linha 9, o ponteiro global A passa a apontar para a nova tabela que acabamos de alocar e preencher.
Digamos que cada execução de uma instrução do tipo A[∗] ← ∗ ou B[∗] ← ∗ custa 1 moeda. (Desta forma, o consumo de tempo será proporcional ao custo em moedas.) Cada execução de Insere-na-Tabela consome 1 moeda no melhor caso e m+1 moedas no pior.
Considere agora uma sequência de n execuções de Insere-na-Tabela, começando com uma tabela vazia:
| 21 _ t ← m ← 0 |
| 22 _ para i crescendo de 1 até n faça |
| 23 ____ lê a |
| 24 ____ Insere-na-Tabela (a) |
Imediatamente antes de cada execução da linha 24, a tabela tem carga m = i−1. Portanto, a execução da linha 24 custa i moedas no pior caso. Assim, o custo total das n execuções não passa de 1+2+⋅⋅⋅+n = (n²+n)/2 moedas. Mas essa cota superior é exagerada: o custo total não passa de 3n moedas, como veremos a seguir.
Antes de cada execução de Insere-na-Tabela a tabela possui um certo estoque de moedas (acumulado ao longo das iterações anteriores). Para dar início à execução Insere-na-Tabela, é preciso acrescentar três moedas ao estoque. Durante a execução, as atribuição nas linhas 7 e 12 consomem parte do estoque deixando um saldo que, como veremos, nunca é negativo. (A ideia é que a primeira das três moedas seja usada para custear a atribuição A[m] ← a na linha 12, a segunda moeda seja usada futuramente para custear a realocação de A[m] e a terceira custeie futuramente a realocação de um dos elementos de A[1..m−1].) Graças a esse protocolo, temos o seguinte invariante:
antes de cada execução de Insere-na-Tabela, a tabela possui pelo menos 2m − t moedas em estoque.
Prova do invariante: A propriedade vale antes da primeira execução de Insere-na-Tabela pois nessa ocasião m e t são nulos. Suponha agora que temos pelo menos 2m − t moedas no início de uma execução qualquer de Insere-na-Tabela. Há três casos a considerar:
Isso encerra a prova. O invariante mostra que toda vez m = t o estoque tem pelo menos m moedas, o que é suficiente para custear a expansão da tabela (linhas 6 a 7). Concluímos assim que a sequência de n execuções de Insere-na-Tabela apenas
3n moedas.
Segue daí que as n execuções de Insere-na-Tabela consomem Ο(n) unidades de tempo. Essa conclusão pode ser resumida dizendo que, no sentido amortizado, cada execução de Insere-na-Tabela na linha 24 consome Ο(1) unidades de tempo, ou seja, uma quantidade de tempo que não depende de n.
Considere agora o comportamento da tabela sob a operação de remoção (= delete) de elementos. Gostaríamos que a carga m da tabela nunca fosse menor que uma certa fração de t, digamos t/4. A operação de remoção de um elemento pode, então, ser descrita como segue:
| Remove-da-Tabela ( ) |
| 11 _ se m ≤ t/4 |
| 12 ____ então B ← Aloca-Tabela (t/2) |
| 13 ____ então para k crescendo de 1 até m faça |
| 14 _______ então B[k] ← A[k] |
| 15 ____ então Libera-Tabela (A) |
| 16 ____ então A ← B |
| 17 ____ então t ← t/2 |
| 18 _ a ← A[m] |
| 19 _ m ← m − 1 |
| 10 _ se m = 0 |
| 11 ____ então Libera-Tabela (A) |
| 12 ____ então t ← 0 |
| 13 _ devolva a |
As linhas 2 a 7 produzem uma contração da tabela; a linha 4, em particular, realoca o elemento A[k]. Na linha 8, o espaço ocupado por A é liberado. Depois da linha 9, o ponteiro global A passa a apontar para a nova tabela que acabamos de alocar e preencher.
Suporemos que em todas as invocações do algoritmo valem as seguintes condições:
Graças a estas condições, o algoritmo nunca será invocado com m = 0. Além disso, o valor da expressão "t/2" nas linhas 2 e 7 será uma potência de 2 (em particular, será inteiro).
A ideia do "t/4" e "t/2" é que depois de uma contração a carga deve dobrar antes que uma expansão se faça necessária (e assim o número de elementos inseridos será suficiente para "pagar" pela expansão). Por outro lado, depois de uma expansão, a carga precisa ser reduzida à metade antes que ocorra uma contração (assim, o número de elementos removidos será suficiente para "pagar" pela contração).
Imagine uma sequência arbitrária de n de inserções e remoções partindo de uma tabela vazia. Isso pode ser descirto assim:
| 31 _ t ← m ← 0 |
| 32 _ para i crescendo de 1 até n faça |
| 33 ____ se m > 0 e condição |
| 34 _______ então a ← Remove-da-Tabela ( ) |
| 35 _______ então imprime a |
| 36 _______ senão lê a |
| 37 _______ senão Insere-na-Tabela (a) |
A condição booleana na linha 33 é arbitrária e portanto, para todos os efeitos, a sequência de inserções e remoções é arbitrária (exceto pela restrição m > 0 que precede toda remoção).
No início de cada execução da linha 33, t é nulo ou uma potência inteira de 2. Além disso, t/4 ≤ m ≤ t.
Digamos que cada execução de uma instrução do tipo A[∗] ← ∗ ou B[∗] ← ∗ em Insere-na-Tabela e Remove-da-Tabela custa 1 moeda. (Desta forma, o consumo de tempo será proporcional ao custo em moedas.) Qual o custo total do processo iterativo nas linhas 32 a 37 no pior caso?
Para fazer a contabilidade, vamos estabelecer o seguinte protocolo. No início de cada iteração, a tabela possui um certo estoque de moedas. Para dar início a qualquer execução de Remove-da-Tabela, é preciso acrescentar duas moedas ao estoque. Para dar início a qualquer execução de Insere-na-Tabela é preciso acrescentar três moedas ao estoque. Durante a execução de qualquer desses dois algoritmos, as atribuição A[∗] ← ∗ e B[∗] ← ∗ consomem parte do estoque deixando um saldo que, como veremos, nunca é negativo. Com esse protocolo, teremos o seguinte invariante: no início de cada iteração, o número de moedas em estoque é
(Prove o invariante.) Com isso, teremos pelo menos m moedas em estoque para custear a expansão da tabela sempre que isso se fizer necessário.
Fica claro agora que o custo total das n iterações não passa de
3n moedas.
Segue daí que as n execuções de Insere-na-Tabela e Remove-da-Tabela consomem Ο(n) unidades de tempo. Essa conclusão pode ser resumida dizendo que, no sentido amortizado, cada execução de Insere-na-Tabela ou Remove-da-Tabela consome Ο(1) unidades de tempo.