Python - Análise Amortizada

A análise amortizada envolve estimar o tempo de execução para a sequência de operações em um programa sem levar em consideração a extensão da distribuição de dados nos valores de entrada. Um exemplo simples é encontrar um valor em uma lista classificada é mais rápido do que em uma lista não classificada. Se a lista já estiver classificada, não importa o quão distribuídos os dados estão. Mas é claro que o comprimento da lista tem um impacto, pois decide o número de etapas que o algoritmo deve percorrer para obter o resultado final.

Portanto, vemos que, se o custo inicial de uma única etapa de obtenção de uma lista ordenada for alto, o custo das etapas subsequentes de localização de um elemento torna-se consideravelmente baixo. Portanto, a análise amortizada nos ajuda a encontrar um limite no tempo de execução do pior caso para uma sequência de operações. Existem três abordagens para a análise amortizada.

• Accounting Method- Envolve atribuir um custo a cada operação realizada. Se a operação real terminar mais rápido do que o tempo atribuído, algum crédito positivo será acumulado na análise. No cenário inverso, será crédito negativo. Para acompanhar esses créditos acumulados, usamos uma pilha ou estrutura de dados em árvore. As operações que são realizadas antecipadamente (como ordenar a lista) têm alto custo amortizado, mas as operações que se atrasam na sequência têm menor custo amortizado à medida que o crédito acumulado é utilizado. Portanto, o custo amortizado é um limite superior do custo real.

• Potential Method- Neste método o crédito guardado é utilizado para operações futuras como função matemática do estado da estrutura de dados. A avaliação da função matemática e o custo amortizado devem ser iguais. Portanto, quando o custo real é maior do que o custo amortizado, há uma diminuição no potencial e ele é usado para operações futuras que são caras.

• Aggregate analysis - Neste método, estimamos o limite superior do custo total de n passos. O custo amortizado é uma divisão simples do custo total e do número de etapas (n).