Tempo Amortizado Constante

O que se entende por "Tempo Amortizado Constante" quando se fala em complexidade de tempo de um algoritmo?

Tempo amortizado explicado em termos simples:

Se você faz uma operação um milhão de vezes, realmente não se importa com o pior ou o melhor caso dessa operação - o que importa é quanto tempo leva no total quando você repete a operação um milhão de vezes .

Portanto, não importa se a operação é muito lenta de vez em quando, desde que "de vez em quando" seja raro o suficiente para que a lentidão seja diluída. Tempo essencialmente amortizado significa "tempo médio gasto por operação, se você realizar muitas operações". O tempo amortizado não precisa ser constante; você pode ter tempo amortizado linear e logarítmico ou qualquer outra coisa.

Vamos dar o exemplo de uma matriz dinâmica dos tapetes, à qual você adiciona novos itens repetidamente. Normalmente, adicionar um item leva tempo constante (ou seja, O(1)). Mas cada vez que a matriz está cheia, você aloca o dobro do espaço, copia seus dados para a nova região e libera o espaço antigo. Supondo que aloque e libere a execução em tempo constante, esse processo de ampliação leva O(n)tempo em que n é o tamanho atual da matriz.

Portanto, cada vez que você aumenta, você gasta cerca de duas vezes mais que o último. Mas você também esperou o dobro do tempo antes de fazê-lo! O custo de cada alargamento pode assim ser "distribuído" entre as inserções. Isso significa que, a longo prazo, o tempo total gasto para adicionar m itens à matriz é O(m)e, portanto, o tempo amortizado (ou seja, tempo por inserção) O(1).

Isso significa que, com o tempo, o pior cenário padrão será O (1), ou tempo constante. Um exemplo comum é a matriz dinâmica. Se já tivermos alocado memória para uma nova entrada, adicioná-la será O (1). Se não o alocamos, faremos isso alocando, digamos, duas vezes o valor atual. Essa inserção específica não será O (1), mas outra coisa.

O que é importante é que o algoritmo garanta que, após uma sequência de operações, as operações caras sejam amortizadas e, dessa forma, tornem toda a operação O (1).

Ou em termos mais estritos,

Existe uma constante c, de modo que, para cada sequência de operações (também uma que termina com uma operação cara) de comprimento L, o tempo não é maior que c * L (Obrigado Rafał Dowgird )

Para desenvolver uma maneira intuitiva de pensar sobre isso, considere a inserção de elementos em uma matriz dinâmica (por exemplo, std::vectorem C ++). Vamos traçar um gráfico, que mostra a dependência do número de operações (Y) necessárias para inserir N elementos na matriz:

Partes verticais do gráfico preto correspondem a realocações de memória para expandir uma matriz. Aqui podemos ver que essa dependência pode ser representada aproximadamente como uma linha. E esta equação de linha é Y=C*N + b( Cé constante, b= 0 no nosso caso). Portanto, podemos dizer que precisamos gastar C*Noperações, em média, para adicionar N elementos à matriz ou C*1operações para adicionar um elemento (tempo constante amortizado).

Encontrei abaixo a explicação da Wikipedia útil, após repetir a leitura por 3 vezes:

Fonte: https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array

"Matriz dinâmica

Análise amortizada da operação Push para uma matriz dinâmica

Considere uma matriz dinâmica que cresce em tamanho à medida que mais elementos são adicionados a ela, como um ArrayList em Java. Se começássemos com uma matriz dinâmica de tamanho 4, levaria tempo constante para inserir quatro elementos nela. No entanto, empurrar um quinto elemento para essa matriz levaria mais tempo, pois a matriz precisaria criar uma nova matriz com o dobro do tamanho atual (8), copiar os elementos antigos para a nova matriz e adicionar o novo elemento. As próximas três operações push levariam tempo constante da mesma forma e a adição subsequente exigiria outra duplicação lenta do tamanho da matriz.

Em geral, se considerarmos um número arbitrário de empurrões n para uma matriz de tamanho n, notamos que as operações push levam tempo constante, exceto a última que leva O (n) tempo para executar a operação de duplicação de tamanho. Como no total de n operações, podemos calcular a média disso e descobrir que, para inserir elementos no array dinâmico, é necessário: O (n / n) = O (1), tempo constante ".

Para meu entendimento como uma história simples:

Suponha que você tenha muito dinheiro. E você deseja empilhá-los em uma sala. E você tem mãos e pernas longas, contanto que você precise agora ou no futuro. E você precisa preencher tudo em um quarto, para que seja fácil trancá-lo.

Então, você vai direto para o final / canto da sala e começa a empilhá-los. Conforme você as empilha, lentamente a sala fica sem espaço. No entanto, ao preencher, foi fácil empilhá-los. Peguei o dinheiro, coloque o dinheiro. Fácil. É O (1). Não precisamos transferir nenhum dinheiro anterior.

Uma vez que o quarto fica sem espaço. Precisamos de outro quarto, que é maior. Aqui existe um problema, já que podemos ter apenas 1 quarto e apenas 1 bloqueio, precisamos mover todo o dinheiro existente nesse quarto para o novo quarto maior. Portanto, mova todo o dinheiro, de uma sala pequena para uma sala maior. Ou seja, empilhe todos eles novamente. Portanto, precisamos mover todo o dinheiro anterior. Então, é O (N). (supondo que N é a contagem total de dinheiro do dinheiro anterior)

Em outras palavras, foi fácil até N, apenas uma operação, mas quando precisamos mudar para uma sala maior, realizamos N operações. Portanto, em outras palavras, se calcularmos a média, é 1 inserção no início e mais 1 movimento enquanto se move para outra sala. Total de 2 operações, uma inserção, um movimento.

Supondo que N seja grande como 1 milhão, mesmo na sala pequena, as 2 operações comparadas a N (1 milhão) não são realmente um número comparável, portanto, é considerado constante ou O (1).

Supondo que quando fazemos tudo o que precede em outra sala maior, e novamente precisamos nos mover. Ainda é o mesmo. digamos, N2 (digamos, 1 bilhão) é uma nova quantidade de contagem de dinheiro na sala maior

Portanto, temos N2 (que inclui N do anterior, pois passamos de uma sala pequena para uma maior)

Ainda precisamos de apenas duas operações, uma é inserida em uma sala maior e outra operação de movimentação para mudar para uma sala ainda maior.

Portanto, mesmo para N2 (1 bilhão), são 2 operações para cada. o que não é nada de novo. Então, é constante, ou O (1)

Portanto, como o N aumenta de N para N2, ou outro, isso não importa muito. Ainda é constante, ou O (1) operações necessárias para cada um dos N.

Agora suponha que você tenha N como 1, muito pequeno, a contagem de dinheiro é pequena e você tem uma sala muito pequena, que caberá apenas 1 contagem de dinheiro.

Assim que você encher o dinheiro na sala, a sala estará cheia.

Quando você for para a sala maior, suponha que ela possa caber apenas mais um dinheiro, total de 2 contagens de dinheiro. Isso significa que o dinheiro anterior foi movido e mais 1. E novamente está preenchido.

Dessa forma, o N está crescendo lentamente, e não é mais constante O (1), pois estamos movendo todo o dinheiro da sala anterior, mas só podemos caber apenas mais 1 dinheiro.

Após 100 vezes, a nova sala comporta 100 contagens de dinheiro anteriores e mais 1 dinheiro que pode acomodar. Isso é O (N), já que O (N + 1) é O (N), ou seja, o grau de 100 ou 101 é o mesmo, ambos são centenas, ao contrário da história anterior, uns para milhões e outros para bilhões .

Portanto, essa é uma maneira ineficiente de alocar salas (ou memória / RAM) para o nosso dinheiro (variáveis).

Portanto, uma boa maneira é alocar mais espaço, com potências de 2.

1º tamanho do quarto = cabe 1 contagem de dinheiro
2º tamanho do quarto = serve 4 contagens de dinheiro
3º tamanho de quarto = serve 8 contagens de dinheiro
4º tamanho de quarto = serve 16 contagens de dinheiro
5º tamanho de quarto = serve 32 contagens de dinheiro
6 tamanho de quarto = serve 64 contagem de dinheiro
7o tamanho do quarto = cabe 128 contagem de dinheiro
8o tamanho do quarto = cabe 256 contagem de dinheiro
9o tamanho do quarto = cabe 512 contagem de dinheiro
10o tamanho do quarto = serve 1024 contagem de dinheiro
11o tamanho do quarto = serve 2.048 contagem de dinheiro
. ..
16º tamanho da sala = cabe 65.536 contagem de dinheiro
...
32º tamanho da sala = cabe 4.294.967.296 contagem de dinheiro
...
64th tamanho da sala = cabe 18.446.744.073,709.551.616 contagem de dinheiro

Por que isso é melhor? Porque parece crescer lentamente no início e mais rápido depois, isto é, comparado com a quantidade de memória em nossa RAM.

Isso é útil porque, no primeiro caso, embora seja bom, a quantidade total de trabalho a ser realizado por dinheiro é fixa (2) e não comparável ao tamanho da sala (N), a sala que ocupamos nos estágios iniciais pode ser muito grande (1 milhão) que não podemos usar totalmente, dependendo de conseguirmos economizar tanto dinheiro no primeiro caso.

No entanto, no último caso, potências de 2, cresce nos limites de nossa RAM. E assim, aumentando a potência de 2, ambas as análises Armotized permanecem constantes e favorecem a RAM limitada que temos até hoje.

As explicações acima se aplicam à Análise Agregada, a idéia de obter "uma média" em várias operações. Não tenho certeza de como eles se aplicam ao método Bankers ou à análise Physicists Methods of Amortized.

Agora. Não tenho exatamente certeza da resposta correta. Mas isso teria a ver com a condição principal dos métodos de ambos os físicos + banqueiros:

(Soma do custo das operações amortizado)> = (Soma do custo real das operações).

A principal dificuldade que enfrento é que, considerando que os custos operacionais amortizados assintóticos diferem do custo normal assintótico, não sei como avaliar a significância dos custos amortizados.

É quando alguém paga um custo amortizado, sei que não é o mesmo que custo assintótico normal. Que conclusões devo tirar do custo amortizado?

Como temos o caso de algumas operações serem sobrecarregadas enquanto outras são subcargas, uma hipótese poderia ser que citar custos amortizados de operações individuais não faria sentido.

Por exemplo: para um heap de fibonacci, citar o custo amortizado de apenas Decreaseing Key como O (1) não faz sentido, pois os custos são reduzidos pelo "trabalho realizado por operações anteriores no aumento do potencial do heap".

OU

Poderíamos ter outra hipótese que justifique os custos amortizados da seguinte forma:

1. Eu sei que a operação cara será precedida por operações MÚLTIPLAS DE BAIXO CUSTO.

2. Para fins de análise, vou sobrecarregar algumas operações de baixo custo, TAIS QUE SEU CUSTO ASSINTOTICO NÃO MUDE.

3. Com essas operações de baixo custo, posso provar que a operação dispendiosa tem um custo menor e assintomático.

4. Assim, eu melhorei / diminuí o limite assintótico do custo de n operações.

Assim, a análise de custo amortizado + os limites de custo amortizado agora são aplicáveis ​​apenas às operações caras. As operações baratas têm o mesmo custo amortizado assintótico do que o custo assintótico normal.

É possível calcular a média de desempenho de qualquer função dividindo o "número total de chamadas de função" no "tempo total gasto para todas as chamadas feitas". Mesmo as funções que demoram mais e mais para cada chamada que você faz podem ser calculadas em média dessa maneira.

Portanto, a essência de uma função que executa Constant Amortized Timeé que esse "tempo médio" atinge um limite que não é excedido à medida que o número de chamadas continua aumentando. Qualquer chamada em particular pode variar em desempenho, mas, a longo prazo, esse tempo médio não continuará aumentando.

Este é o mérito essencial de algo que se desempenha Constant Amortized Time.