O que é análise amortizada de algoritmos? [fechadas]

Como é diferente da análise assintótica? Quando você o usa e por quê?

Eu li alguns artigos que parecem ter sido bem escritos, como estes:

• http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf

• http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf

mas ainda não entendi totalmente esses conceitos.

Então, alguém pode simplificar isso para mim?

A análise amortizada não multiplica ingenuamente o número de invocações com o pior caso para uma invocação.

Por exemplo, para uma matriz dinâmica que dobra de tamanho quando necessário, a análise assintótica normal apenas concluiria que adicionar um item a ela custa O (n), porque pode ser necessário aumentar e copiar todos os elementos para a nova matriz. A análise amortizada leva em consideração que, para ter que crescer, n / 2 itens devem ter sido adicionados sem causar um crescimento desde o crescimento anterior, então adicionar um item realmente leva apenas O (1) (o custo de O (n) é amortizado em n / 2 ações).

A análise amortizada não é o mesmo que um "desempenho médio" - a análise amortizada oferece uma garantia sólida sobre o que o desempenho fará se você fizer tantas ações.

Existem muitas respostas para "o quê", mas nenhuma para "por quê".

Como todo mundo já disse, a análise assintótica trata de como o desempenho de uma determinada operação é dimensionado para um grande conjunto de dados. A análise amortizada é sobre como a média do desempenho de todas as operações em um grande conjunto de dados é dimensionada. A análise amortizada nunca fornece limites piores do que os assintóticos e, às vezes, fornece limites muito melhores.

Se você está preocupado com o tempo total de execução de um trabalho mais longo, provavelmente você se preocupa com os melhores limites da análise amortizada. É por isso que as linguagens de script (por exemplo) costumam ficar felizes em aumentar matrizes e tabelas de hash por algum fator, mesmo que seja uma operação cara. (O crescimento pode ser uma O(n)operação, mas amortizado é O(1)porque você raramente o faz.)

Se você estiver fazendo programação em tempo real (as operações individuais devem ser concluídas em um tempo previsível), os melhores limites da análise amortizada não importam. Não importa se a operação em média foi rápida, se você falhou em terminar a tempo de voltar e ajustar a serra de fita antes de cortar muito ...

O que importa no seu caso depende exatamente de qual é o seu problema de programação.

Análise assintótica

Este termo se refere à análise do desempenho do algoritmo sob a suposição de que os dados nos quais o algoritmo opera (a entrada ) são, em termos leigos, "grandes o suficiente para que aumentá-los não altere a conclusão". Embora o tamanho exato da entrada não precise ser especificado (precisamos apenas de um limite superior), o conjunto de dados em si deve ser especificado.

Observe que até agora falamos apenas sobre o método de análise; não especificamos exatamente qual quantidade estamos analisando (complexidade do tempo? complexidade do espaço?), e nem especificamos em qual métrica estamos interessados ​​(pior caso? melhor caso? média?).

Na prática, o termo análise assintótica comumente se refere ao limite superior da complexidade de um algoritmo, ou seja, o pior caso de desempenho medido pelo tempo total de execução, que é representado pela notação big-Oh (por exemplo, um algoritmo de classificação pode ser O(nlogn)).

Análise amortizada

Este termo se refere à análise do desempenho do algoritmo com base em uma sequência específica de operações que visa o pior cenário - ou seja, a análise amortizada implica que a métrica é o pior caso de desempenho (embora ainda não diga qual quantidade está sendo medida ) Para realizar essa análise, precisamos especificar o tamanho da entrada, mas não precisamos fazer nenhuma suposição sobre sua forma.

Em termos leigos, a análise amortizada é escolher um tamanho arbitrário para a entrada e, em seguida, "reproduzir" o algoritmo. Sempre que uma decisão que depende da entrada deve ser tomada, o pior caminho é escolhido¹. Depois que o algoritmo foi executado até a conclusão, dividimos a complexidade calculada pelo tamanho da entrada para produzir o resultado final.

¹note: Para ser preciso, o pior caminho que é teoricamente possível . Se você tem um vetor que dobra de tamanho dinamicamente cada vez que sua capacidade se esgota, "pior caso" não significa supor que ele precisará dobrar a cada inserção, porque as inserções são processadas como uma sequência. Temos permissão para (e de fato devemos) usar o estado conhecido para eliminar matematicamente o máximo de casos "ainda piores" que pudermos, mesmo enquanto a entrada permanecer desconhecida.

A diferença mais importante

A diferença crítica entre a análise assintótica e amortizada é que a primeira depende da própria entrada, enquanto a última depende da sequência de operações que o algoritmo executará.

Portanto:

• a análise assintótica permite-nos afirmar que a complexidade do algoritmo quando é dada uma entrada de melhor / pior / caso médio de tamanho que se aproxima de N é limitada por alguma função F (N) - onde N é uma variável
• a análise amortizada nos permite afirmar que a complexidade do algoritmo quando recebe uma entrada de características desconhecidas, mas tamanho N conhecido não é pior do que o valor de uma função F (N) - onde N é um valor conhecido

A resposta para isso é definida de forma sucinta pela primeira frase do capítulo Análise Amortizada do livro - Introdução aos Algoritmos:

Em uma análise amortizada , o tempo necessário para executar uma sequência de operações de estrutura de dados é calculado sobre todas as operações realizadas.

Representamos a complexidade do crescimento de um programa por análise assintótica - que limita o crescimento do programa por uma função e define o pior, o melhor ou o caso médio disso.

Mas isso pode ser enganoso nos casos em que há apenas um caso em que a complexidade do programa atinge o pico, mas, em geral, o programa não exige muitos cálculos.

Portanto, faz mais sentido calcular a média do custo em uma sequência de operações, mesmo que uma única operação possa ser cara. Esta é a análise amortizada!

A análise amortizada é uma alternativa à técnica assintótica usada para calcular a complexidade. Ajuda-nos a calcular uma complexidade mais verdadeira em termos de praticidade, de forma a comparar e decidir entre dois ou mais algoritmos.

A melhor referência que encontrei até agora para compreender a análise amortizada de algoritmos está no livro Introdução aos Algoritmos , terceira edição, capítulo 17: "Análise Amortizada". Está tudo lá, explicado muito melhor do que o que pode ser encontrado em uma postagem do Stack Overflow. Você encontrará o livro na biblioteca de qualquer universidade decente.

A análise assintótica regular examina o desempenho de uma operação individual assintoticamente, em função do tamanho do problema. A notação O () é o que indica uma análise assintótica.

A análise amortizada (que também é uma análise assintótica) analisa o desempenho total de várias operações em uma estrutura de dados compartilhada .

A diferença é que a análise amortizada normalmente prova que o cálculo total necessário para M operações tem uma garantia de desempenho melhor do que M vezes o pior caso para a operação individual.

Por exemplo, uma operação individual em uma árvore splay de tamanho N pode levar até O (N) tempo. No entanto, uma sequência de M operações em uma árvore de tamanho N é limitada pelo tempo O (M (1 + log N) + N log N), que é aproximadamente O (log N) por operação. No entanto, observe que uma análise amortizada é muito mais estrita do que uma análise de "caso médio": ela prova que qualquer sequência possível de operações satisfará seu pior caso assintótico.

A análise amortizada lida com o custo total em várias execuções da rotina e os benefícios que podem ser obtidos com isso. Por exemplo, pesquisar uma matriz não classificada de n itens para uma única correspondência pode levar até n comparações e, portanto, é o (n) complexidade. No entanto, se soubermos que o mesmo array será pesquisado por m itens, repetir a tarefa total teria complexidade O (m * n). No entanto, se classificarmos o array antecipadamente, o custo é O (n log (n)), e pesquisas sucessivas levam apenas O (log (n)) para um array classificado. Assim, o custo amortizado total para m elementos usando esta abordagem é O (n * log (n) + m * log (n)). Se m> = n, isso equivale a O (n log (n)) por pré-classificação em comparação com O (n ^ 2) para não classificar. Assim, o custo amortizado é mais barato.

Simplificando, gastando um pouco mais no início, podemos economizar muito mais tarde.