O que é análise amortizada? E como isso pode me ajudar a obter as garantias de pior desempenho nos meus programas?
Eu estava lendo que as técnicas a seguir podem ajudar o programador a obter garantias de desempenho de pior caso (ou seja, em minhas próprias palavras: garantir que o tempo de execução de um programa não exceda o tempo de execução no pior elenco):
- Algoritmos randomizados (por exemplo, o algoritmo quicksort é quadrático no pior dos casos, mas ordenar aleatoriamente a entrada fornece uma garantia probabilística de que seu tempo de execução é linearitmico)
- Sequências de operações (nossa análise deve levar em conta os dados e a sequência de operações executadas pelo cliente)
- Análise Amortizada (outra maneira de fornecer uma garantia de desempenho é amortizar o custo, mantendo o controle do custo total de todas as operações, dividido pelo número de operações. Nesse cenário, podemos permitir algumas operações caras, mantendo o custo médio Em outras palavras, distribuímos o custo de poucas operações caras, atribuindo uma parte dela a cada um de um grande número de operações baratas)
O autor mencionou o uso de redimensionar a estrutura de dados da matriz para Stack como um exemplo de como obter análise amortizada, mas ainda não entendo o que é a análise amortizada e como ela pode realmente ser implementada (estrutura de dados? Algoritmo?) Para obter o pior desempenho. garantias de desempenho
fonte