Tempo Amortizado Constante

O que significa “Tempo Amortizado Constante” quando se fala em complexidade temporal de um algoritmo?

    Tempo amortizado explicado em termos simples:

    Se você faz uma operação, digamos um milhão de vezes, você não se importa com o pior caso ou com o melhor caso dessa operação – o que importa é quanto tempo é gasto 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ê fizer 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 pegar o exemplo de um array dynamic, ao qual você adiciona novos itens repetidamente. Normalmente, adicionar um item leva tempo constante (ou seja, O(1) ). Mas cada vez que o array está cheio, você aloca o dobro do espaço, copia seus dados para a nova região e libera o espaço antigo. Assumindo que aloca e libera a execução em tempo constante, esse processo de ampliação leva O(n) tempo em que n é o tamanho atual da matriz.

    Então, cada vez que você aumenta, você leva o dobro do tempo que a última ampliação. Mas você também esperou o dobro disso antes de fazer isso! O custo de cada ampliação pode assim ser “espalhado” entre as inserções. Isso significa que, a longo prazo, o tempo total gasto para adicionar m itens à matriz é O(m) , e assim o tempo amortizado (ou seja, tempo por inserção) é O(1) .

    Isso significa que com o tempo, o pior cenário será o padrão O (1) ou o tempo constante. Um exemplo comum é o array dynamic. Se já alocamos memory para uma nova input, a adição será O (1). Se não tivermos alocado, faremos isso alocando, digamos, o dobro do valor atual. Esta inserção particular não será O (1), mas sim algo mais.

    O importante é que o algoritmo garanta que, após uma seqüência de operações, as operações caras serão amortizadas e, assim, renderizando toda a operação O (1).

    Ou em termos mais estritos,

    Existe uma constante c, tal que para cada sequência de operações (também uma terminando com uma operação dispendiosa) 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 matriz dinâmica (por exemplo, std::vector em C ++). Vamos traçar um gráfico que mostre a dependência do número de operações (Y) necessárias para inserir N elementos no array:

    enredo

    Partes verticais do grafo preto correspondem a realocações de memory para expandir um array. 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, em média, operações C*N para adicionar N elementos ao array, ou operações C*1 para adicionar um elemento (tempo constante amortizado).

    Eu encontrei abaixo explicação útil Wikipedia, depois de 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 um array dynamic que cresce em tamanho à medida que mais elementos são adicionados a ele, como um ArrayList em Java. Se começássemos com uma matriz dinâmica de tamanho 4, levaria tempo constante para enviar quatro elementos para ela. Ainda assim, o envio de um quinto elemento para esse array levaria mais tempo, pois o array teria que criar um novo array com o dobro do tamanho atual (8), copiar os elementos antigos no novo array e depois adicionar o novo elemento. As próximas três operações de envio de maneira similar levariam tempo constante e, em seguida, a adição subsequente exigiria outra duplicação lenta do tamanho da matriz.

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

    Para mim, uma história simples:

    Suponha que você tenha muito dinheiro. E você quer empilhá-los em uma sala. E você tem mãos e pernas longas, tanto quanto você precisa agora ou no futuro. E você tem que preencher tudo em um quarto, então é fácil bloqueá-lo.

    Então, você vai direto para o final / canto da sala e começa a empilhá-los. À medida que você as empilha, lentamente a sala ficará sem espaço. No entanto, conforme você preenche, é fácil empilhá-los. Pegue o dinheiro, coloque o dinheiro. Fácil. É O (1). Nós não precisamos mover nenhum dinheiro anterior.

    Uma vez que o espaço fica sem espaço. Precisamos de outro quarto, que seja maior. Aqui há um problema, já que podemos ter apenas um quarto para que possamos ter apenas um bloqueio, precisamos mover todo o dinheiro existente naquele quarto para o novo quarto maior. Então, mova todo o dinheiro, da pequena sala para a sala maior. Ou seja, empilhe todos eles novamente. Então, nós precisamos mover todo o dinheiro anterior. Então, é O (N). (assumindo N é contagem total de dinheiro de dinheiro anterior)

    Em outras palavras, foi fácil até N, apenas 1 operação, mas quando precisamos nos mudar para uma sala maior, nós fizemos N operações. Então, em outras palavras, se calcularmos a média, é 1 inserção no começo e mais 1 movimento enquanto nos movemos para outra sala. Total de 2 operações, uma inserção, um movimento.

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

    Assumindo quando fazemos todos os itens acima em outra sala maior, e novamente precisamos nos mover. Ainda é o mesmo. digamos, N2 (digamos, 1 bilhão) é uma nova quantia de dinheiro na sala maior

    Então, nós temos N2 (que inclui N do anterior, já que nos movemos de pequeno para maior)

    Ainda precisamos de apenas 2 operações, uma é inserida em uma sala maior e, em seguida, outra operação de movimentação para se mover para uma sala ainda maior.

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

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


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

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

    Quando você vai para a sala maior, suponha que só pode caber mais um dinheiro, total de 2 pontos em dinheiro. Isso significa que o dinheiro movido anterior e mais 1. E mais uma vez é preenchido.

    Desta forma, o N está crescendo lentamente, e não é mais constante O (1), já que estamos movimentando todo o dinheiro da sala anterior, mas só podemos encheckboxr apenas mais um dinheiro.

    Depois de 100 vezes, o novo quarto se encheckbox 100 de dinheiro do anterior e mais um 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 memory / RAM) para nosso dinheiro (variables).


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

    Tamanho do quarto 1 = cabe uma contagem de dinheiro
    Tamanho do quarto 2 = cabe 4 de dinheiro
    Tamanho do quarto 3 = cabe 8 contagem de dinheiro
    Tamanho quarto 4 = cabe 16 contagem de dinheiro
    Tamanho do quarto 5 = cabe 32 de dinheiro
    Tamanho da sala 6 = se encheckbox 64 contagem de dinheiro
    Tamanho da sala 7 = cabe 128 contagem de dinheiro
    Tamanho do quarto 8 = cabe 256 de dinheiro
    Tamanho do quarto 9 = cabe 512 de dinheiro
    Tamanho do quarto 10 = se encheckbox 1024 contagem de dinheiro
    Tamanho do quarto 11 = se encheckbox 2.048 contagem de dinheiro

    Tamanho do quarto 16 = cabe 65.536 contagem de dinheiro

    Tamanho do quarto 32 = se encheckbox 4.294.967.296 de dinheiro

    64º tamanho da sala = cabe 18.446.744.073.709.551.616 de dinheiro

    Por que isso é melhor? Porque parece crescer lentamente no começo, e mais rápido depois, isto é, comparado com a quantidade de memory em nossa RAM.

    Isso é útil porque, no primeiro caso, embora seja bom, a quantidade total de trabalho a ser feito por dinheiro é fixa (2) e não é comparável ao tamanho do quarto (N), o espaço que tomamos nos estágios iniciais pode ser muito grande (1 milhão) que nós podemos não usar completamente dependendo de se nós podemos adquirir tanto dinheiro para economizar a todos no primeiro caso.

    No entanto, no último caso, potências de 2, cresce nos limites da nossa RAM. E assim, aumentando em potências de 2, tanto a análise Armotizada permanece constante e é amigável para a RAM limitada que temos a partir de hoje.

    As explicações acima aplicam-se à Análise Agregada, a ideia de obter “uma média” em várias operações. Não tenho certeza de como eles se aplicam ao método de banqueiros ou aos methods físicos de análise amortizada.

    Agora. Não tenho certeza da resposta correta. Mas isso teria a ver com a condição de princípio dos dois methods de Physics + Banker:

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

    A principal dificuldade que enfrento é que, dado que os custos assintóticos amortizados das operações diferem do custo normal-assintótico, não sei como avaliar a importância dos custos amortizados.

    É quando alguém me dá um custo amortizado, sei que não é o mesmo que o custo normal-assintótico. Que conclusões devo extrair do custo amortizado?

    Uma vez que temos o caso de algumas operações sendo sobrecarregadas, enquanto outras operações são subcarregadas, uma hipótese poderia ser que citar custos amortizados de operações individuais não teria sentido.

    Por exemplo: Para uma pilha de Fibonacci, citar o custo amortizado de apenas Decreasing-Key como O (1) não tem sentido, pois os custos são reduzidos pelo “trabalho feito por operações anteriores no aumento do potencial da pilha”.

    OU

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

    1. Eu sei que a operação cara vai precedida por operações de MUITO CUSTO BAIXO.

    2. Para fins de análise, vou sobrecarregar algumas operações de baixo custo, TAL COMO SEU CUSTO ASTÉMTICO NÃO MUDA.

    3. Com essas operações de baixo custo aumentadas, POSSO PROVAR QUE A OPERAÇÃO GOSTA TEM UM CUSTO ASSIMÉTRICO MENOR.

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

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