Quantas cópias são necessárias para aumentar uma matriz?

Estou lendo uma análise sobre matrizes dinâmicas (do manual do algoritmo do Skiena).
Ou seja, quando temos uma estrutura de matriz e cada vez que estamos sem espaço, alocamos uma nova matriz com o dobro do tamanho do original.

Ele descreve o desperdício que ocorre quando a matriz precisa ser redimensionada.
Diz que (n / 2) +1 a n será movido no máximo uma vez ou não será. Isto está claro.
Em seguida, descrevendo que metade dos elementos se move uma vez, um quarto dos elementos duas vezes e assim por diante, o número total de movimentos M é dado por:

Parece-me que adiciona mais cópias do que realmente acontece.

Por exemplo

se tivermos o seguinte:

array of 1 element
+--+
|a |
+--+

double the array (2 elements)  
+--++--+  
|a ||b |  
+--++--+  

double the array (4 elements)  
+--++--++--++--+  
|a ||b ||c ||c |  
+--++--++--++--+  

double the array (8 elements)  
+--++--++--++--++--++--++--++--+    
|a ||b ||c ||c ||x ||x ||x ||x |  
+--++--++--++--++--++--++--++--+    

double the array (16 elements)  
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+    
|a ||b ||c ||c ||x ||x ||x ||x ||  ||  ||  ||  ||  ||  ||  ||  |   
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+   

Temos o elemento x copiado 4 vezes, o elemento c copiado 4 vezes, o elemento b copiado 4 vezes e um elemento copiado 5 vezes, de modo que o total é 4 + 4 + 4 + 5 = 17 cópias / movimentos.

Mas, de acordo com a fórmula, deveríamos ter 1 * (16/2) + 2 * (16/4) + 3 * (16/8) + 4 * (16/16) = 8 + 8 + 6 + 4 = 26 cópias de elementos para a ampliação da matriz para 16 elementos.

Isso é algum erro ou o objetivo da fórmula é fornecer uma aproximação aproximada do limite superior? Ou estou entendendo algo errado aqui?

Primeiro, b é movido 3 vezes e a é movido 4 vezes, o que fornece um total de 4 + 4 + 3 + 4 = 15 cópias.

Eu acho que a fórmula deve ser preenchida com n = 8: 1 * (8/2) (x é copiado uma vez) + 2 * (8/4) (c é copiado duas vezes) + 3 * (8/8) (b é copiado três vezes) = 11. Em outras palavras, a fórmula parece estar faltando um termo "+ log ₂ n + 1" além da soma em si.

O que me parece ser uma maneira muito mais natural de contar o número de movimentos é contar o número de elementos movidos por cópia:

soma de i = 1 a i = teto (log ₂ n): 2 ^i-1

No seu caso, n = 16, então teto (log ₂ 16) = 4 e a soma acima é: 2 ⁰ +2 ¹ +2 ² +2 ³ = 1 + 2 + 4 + 8 = 15.

Vou ver se consigo encontrar este manual do algoritmo do Skiena para ver se o corrigi.

Atualização: Encontrei a peça no manual do algoritmo de Skiena. Parece que falta um termo na soma que ele usa lá. No entanto, a conclusão está correta:

M = soma de i = 1 a i = teto (log ₂ n): 2 ^i-1 = soma de i = 0 a i = teto (log ₂ n) - 1: 2 ⁱ = 2 ^{teto (log ₂ n) - 1 + 1} <= (2 ^{log ₂ n + 1-1 + 1} ) = 2 * n

(Gostaria de poder formatar essas fórmulas de uma maneira mais agradável para você)

O ponto principal deste parágrafo parece ser o exemplo de análise amortizada . Métodos como o método potencial criariam um argumento melhor (menos ad hoc) por que as matrizes dinâmicas funcionam muito bem, mas esse método é um pouco avançado.

Se você está convencido de que há um erro neste livro, considere entrar em contato com o autor sobre isso (de uma maneira construtiva, é claro - o livro tem muitas páginas, e é difícil corrigir tudo o que há de mais atual e sempre há uma chance de o livro estar certo e nós dois errarmos). Eu não encontrei este em particular na errata.

Nos níveis mais baixos de contagem de blocos, é improvável que ocorra uma alocação de memória. Os gerenciadores de memória lidam com blocos de memória e alocam rotineiramente blocos maiores de memória do que a solicitação de alocação solicitada automaticamente.

Da mesma forma, a implementação de uma classe de matriz provavelmente arredondará alocações para permitir alguns elementos adicionais.

EDITAR:

Em uma reflexão mais aprofundada, é improvável que as cópias reais ocorram conforme você as descreve. Os processadores geralmente possuem um comando de cópia de bloco e usariam uma única instrução de montagem para copiar os dados da matriz como um único bloco de memória para o novo endereço.

Eu acredito que a fórmula dada no livro é simplesmente incorreta. O imultiplicador deve ser retirado da fórmula para corrigi-lo.

Vamos pegar o exemplo do autor e chamar a matriz de 1 elemento matriz-1, a matriz de 2 elementos - array-2, a matriz de 4 elementos - array-4e assim por diante.

Portanto, de acordo com o livro, para este exemplo em particular, o número de cópias é regido pela seguinte fórmula:

M = 1⋅8 + 2⋅4 + 3⋅2 + 4⋅1

O primeiro termo da soma 1⋅8é para copiar array-8'sitens para array-16.

Copiamos os array-4'sitens (a, b, c, c)duas vezes. Uma vez do array-4para array-8. E então ao copiar array-8'sitens para array-16nós copiar (a, b, c, c)itens para o segundo tempo. Por conseguinte para o livro, por conseguinte, o segundo termo: 2⋅4.

Mas agora observe que o 1⋅8termo já leva em consideração a cópia de (a, b, c, c)itens de array-8para array-16. Consequentemente, o 2⋅4termo não deve incluir o 2multiplicador.

A mesma lógica se aplica a todos os outros termos. E assim, multiplicar por ié um erro.