Por que minha prova de complexidade de tempo assintomático de uma matriz dinâmica usando o método contábil recebendo uma resposta errada?

Question

Eu tive problemas para formatar os símbolos de somação, por isso, se alguém sabe como fazer corretamente, sinta-se à vontade para editar.

Acabei de ler o capítulo de análise assintomática dos Clrs. Enquanto a agregação e o método potencial são claros para mim, pensei que deveria fazer alguma prática extra com o método contábil. Meu objetivo era provar que se você tiver um tamanho de matriz 1, e quando encher, você o dobro do tamanho, resulta em uma complexidade de tempo de O (1) por operação. Usando a análise agregada, aqui está a prova que eu inventei:

Se você ligar para anexar n vezes, então a complexidade de tempo seria esta:

$ \ sum_ {i= 1} ^ {\ log n} \ frac {1} {2 ^ i} $

que é menor que

$ \ sum_ {i= 1} ^ {+ \ infty} \ frac {1} {2 ^ i} $

O que é igual a $ 2N $ . Assim, a complexidade de tempo para todas as operações N será O (n), então a complexidade de tempo para uma única operação é O (1).

No entanto, se o tamanho começar em 1, então adiciona por 1 em vez de multiplicar por 2 (significado, o tamanho começa 1, então se torna 2, então se torna 3, etc ...) então a complexidade de tempo deve ser O (n ), que eu uso a análise agregada. $ \ sum_ {i= 1} ^ {n} (i + 1) $

O extra 1 vem de realmente colocar o próximo elemento. Isto é igual a cerca de (N (N + 2)) / 2 ou O (n ^ 2) para todas as operações N e O (n) para uma única operação, que está correta. No entanto, usando o método contábil eu recebo outra resposta. O custo real de colocar um elemento é 1, e o custo assintomático que eu defini é 2. Assim, a primeira vez custa 2, e a segunda chamada a cópia não assume algum tempo extra porque eu pré-prei-lo antes, e o custo extra de Colocar esse elemento é 2. Então, torna-se:

$ \ sum_ {i= 1} ^ {n} 2 $

Qual é igual a O (n) para todas as operações totais e O (1) para uma única operação. Esta não é a saída correta. De onde eu dou errado e como posso consertar isso?

Answer 1

Em primeiro lugar, sua primeira análise agregada deve ler $ \ sum_ {i= 1} ^ {\ log n} 2 ^ i= 2 ^ {\ log n + 1} - 2 <2N $ .(O que você escreveu não faz sentido desde $ \ sum_ {i= 1} ^ \ infty \ frac {1} {2 ^ i} \ le 1 $ , quesignificaria que a complexidade agregada é limitada superior por uma constante independentemente do número de operações).

Então, em sua última análise, você não pode simplesmente colocar um crédito extra em cada elemento porque só pagaria por da primeira vez que tal elemento é copiado (ou seja, apenas para a próxima inserção).