Análise amortizada

Na ciência da computação, análise amortizada é um método para analisar a complexidade de tempo de um algoritmo ou quantos recursos computacionais, especialmente de tempo ou de memória no contexto de programas de computadores, ele leva para executar. Diferente das outras análises que focam no tempo de execução no pior caso, a análise amortizada examina como um algoritmo irá se comportar na prática ou na média.^[1]

Enquanto certas operações de um dado algoritmo tenham um grande custo em recursos, outras operações talvez não sejam tão custosas. A análise amortizada considera os dois tipos de operações juntos. Isso pode cobrir tipos diferentes de dados de entrada, tamanho da entrada, e outros fatores que afetam o desempenho do algoritmo.^[2]

História

A análise amortizada inicialmente surgiu de um método chamado de análise agregada, que hoje é incorporada pela análise amortizada. No entanto, essa técnica foi primeiramente formalmente introduzida por Robert Tarjan em 1985 em sua publicação Amortized Computational Complexity, na qual ele comentou a necessidade de uma forma mais útil de análise de algoritmos do que os métodos probabilístico que eram normalmente mais usados. Amortização foi inicialmente usada para tipos muito específicos de algoritmos, particularmente aqueles que envolviam árvores binárias e operações de união. No entanto, agora é muito presente e usada para a análise de vários outros algoritmos também.

Método

Esse método requer conhecimento de quais sequencias de operações são possíveis. Isso normalmente é o caso com estruturas de dados, que possuem estado persistente entre operações. A ideia básica é que uma operação no pior caso pode alterar o estado de tal forma que o pior caso não possa ocorrer novamente por um longo tempo, assim "amortizando" seu custo.

Geralmente existem três métodos para realizar a análise amortizada: o método de análise agregada, o método contabilizador e o método potencial. Todos esses dão as mesmas respostas e a diferença em seu uso é principalmente circunstancial e por preferência individual.^[3]

O método de análise agregada determina o limitante superior T(n) no custo total de uma sequencia de n operações, e então calcula o custo amortizado como sendo T(n) / n.^[3]
O método contabilizador determina o custo individual de cada operação, combinando o tempo de sua execução imediata com a influencia no tempo de execução em futuras operações. Normalmente, muitas operações de curta execução acumulam uma "dívida" de estados desfavoráveis em pequenos incrementos, enquanto raras operações de longa execução a diminuem drasticamente.^[3]
O método potencial é parecido com o método contabilizador, mas com operações iniciais "sobretaxadas" para cobrir o custo não contabilizado de operações futuras.^[3]

Exemplos

Arranjo dinâmico

Considere um arranjo dinâmico que cresce em tamanho com cada elemento adicionado como um ArrayList em Java. Se nós começarmos com um arranjo dinâmico de tamanho 4, ele terá um tempo constante para inserir 4 elementos dentro dele. Entretanto inserir um quinto elemento nesse arranjo tomará mais tempo, pois o arranjo terá que criar criar um novo arranjo de duas vezes o tamanho atual (8), copiar todos os elementos antigos para o novo e apenas então adicionar o novo elemento. As próximas três inserções iriam tomar tempo constante até que a quarta inserção iria exigir mais tempo para dobrar o tamanho do arranjo novamente.

Em geral. se considerássemos um número arbitrário de inserções n em um arranjo de tamanho n, nós notaríamos que todas as operações de inserção tomariam tempo constante menos a última, que tomaria tempo O(n) para realizar a operação de dobrar o tamanho. Como existiriam n operações nós podemos pegar a média disso e concluir que a inserção de elementos em um arranjo dinâmico leva : $O({\tfrac {n}{n}})=O(1)$ , tempo constante.^[3]

Fila

Vamos olhar para a implementação em Ruby de uma Fila, uma estrutura de dados FIFO :

class Queue
  def initialize
    @input = []
    @output = []
  end

  def enqueue(element)
    @input << element
  end

  def dequeue
    if @output.empty?
      while @input.any?
        @output << @input.pop
      end
    end

    @output.pop
  end
end

A operação de enfileiramento é sempre de tempo constante, pois ela apenas insere um elemento no arranjo de entrada. Essa operação não depende dos tamanhos de entrada ou saída, então apenas toma tempo constante.

Entretanto a operação de desenfileirar é mais complicada. Se o arranjo de saída já tiver elementos nele, então o programa leva tempo constante para realizar essa operação. Mas se a saída estiver vazia, o tempo para adicionar todos os elementos do arranjo de entrada para o arranjo de saída será de tempo O(n), com n sendo o tamanho do arranjo de entrada. Agora, se nós já copiamos os n elementos da entrada, então podemos realizar n operações de desenfileirar com cada uma sendo de tempo constante antes de termos que realizar outra operação custosa de copiar todos os elementos da entrada novamente. Assim, em prática, o tempo de execução amortizado de desenfileirar é de O(1).^[4]

Uso geral

Em uso geral, um "algoritmo amortizado" é aquele que em que uma análise amortizada mostrou um bom desempenho.

Referências

↑ «Lecture 7: Amortized Analysis» (PDF). cs.cmu.edu/. Consultado em 14 de março de 2015
↑ Rebecca Fiebrink (2007), Amortized Analysis Explained (PDF), consultado em 3 de maio de 2011
↑ ^a ^b ^c ^d ^e «Lecture 20: Amortized Analysis». cs.cornell.edu/. Cornell University. Consultado em 14 de março de 2015
↑ Grossman, Dan. «CSE332: Data Abstractions» (PDF). cs.washington.edu. Consultado em 14 de março de 2015