Análise Amortizada

Playlists

1 Análise amortizada

Figuras: trinityscsp e Wikipedia

A análise do odômetro binário é muito parecida com o decimal.

  • Pode ser visto como uma série de incrementos sucessivos.
  • Cada mudança de dígito tem um custo real que vamos convencionar como sendo \(1\).

Figura: [CLRS]

  • Note que o custo acumulado nunca é maior que o dobro de operações.
  • Poderíamos até considerar que sendo o contador de \(k\) bits, o custo por incremento será \(O(k)\) e para uma sequência de \(n\) incrementos, será \(O(nk)\).
  • O problema é que estamos exagerando, a maior parte das operações nem toca em todos os bits!
  • O bit 0 é modificado a cada incremento
  • O bit 1 é modificado a cada 2 incrementos
  • O bit 2 é modificado a cada 4 incrementos
  • …

Logo para uma sequência de \(n\) (\(n \le 2^{k}\)) incrementos (com o contador a partir do \(0\)) o total de modificações é:

\[\sum_{i=0}^{\lfloor \lg n\rfloor}\left\lfloor\dfrac{n}{2^i}\right\rfloor < n\sum_{i=0}^{\infty}\frac{1}{2^i} = 2n\]

1.1 Análise amortizada

  • A noção da análise amortizada vem da seguinte observação:

    • Dada uma sequência de operações, estamos interessados no tempo total de execução da sequência e não de cada operação individualmente.

  • Em outras palavras, queremos que a execução da sequência toda de \(n\) operações seja, por exemplo, \(O(n)\) mas não nos importamos se alguma das operações não for \(O(1)\).

  • Em outras palavras, o custo médio de cada operação e, portanto, o custo amortizado de cada operação é \(O(1)\).

1.2 Revisitando filas

  • Há dois métodos consagrados para a análise amortizada:
    • O método do banqueiro ou de contabilidade;
    • O método do físico ou potencial.

Vamos apresentar uma estrutura de dados para filas e exemplificar como podemos empregar o método do banqueiro1.

A implementação funcional mais comum de filas envolve o uso de duas listas f e r.

  • f contém os elementos no início (front) da fila
    • Mantém os elementos na mesma ordem da fila
  • r contém os elementos do final (rear) da fila
    • Mantém os elementos na ordem inversa da fila

--              f    r
type Fila a = ([a], [a])

A cabeça da lista está localizada em f, então tanto a função head quanto a função tail operam neste ponto

head :: Fila a -> a
head (x:f, r) = x

tail :: Fila a -> Fila a
tail (x:f, r) = (f, r)

De maneira semelhante, o último elemento da fila é o primeiro elemento de r, logo snoc2 simplesmente adiciona um elemento à r.

snoc :: Fila a -> a -> Fila a
snoc (f, r) x = (f, x : r)

1.3 O invariante

  • Elementos são adicionados em r e retirados de f.
  • Assim, em algum momento eles tem que ser migrados.
  • Faremos a migração se após uma operação houver ao menos um elemento na fila mas f estiver vazio (ou seja, há elementos em r).
  • O objetivo é manter o seguinte invariante: f estará vazio se e somente se r também estiver vazio (ou seja, a fila toda está vazia).
    • Note que se isso não fosse verdade, se f estivesse vazio e r não, então o primeiro elemento da fila seria o último elemento de r (acesso em tempo \(O(n)\)).
    • Este invariante garante que head (e tail) sempre rodam em tempo \(O(1)\).

Mantendo o invariante

Para isso precisaremos adaptar as funções que alteram a fila (tail e snoc). Vamos usar uma função auxiliar que faz o trabalho:

check :: Fila a -> Fila a
check ([], r) = (rev r, [])
check q = q

snoc :: Fila a -> a -> Fila a
snoc (f, r) x = checkf (f, x : r)

tail :: Fila a -> Fila a
tail (x:f, r) = checkf (f, r)

1.4 O método do Banqueiro

  • Para provar um limite amortizado, é preciso definir o custo amortizado de cada operação e provar que, para qualquer sequência de operações, o custo total amortizado das operações é um limite superior no custo total real.

\[\sum_{i=1}^{n} a_i \ge \sum_{i=1}^{n}t_i\]

Onde \(a_i\) é o custo amortizado da operação \(i\), \(t_i\) é o custo real da operação \(i\) e \(n\) é o número total de operações.

  • Na verdade na prática acabamos quase sempre provando algo mais forte que é:

\[\sum_{i=1}^{j} a_i \ge \sum_{i=1}^{j}t_j\]

Onde \(j \le n\) indica que a qualquer momento a soma das operações amortizadas é um limite superior ao custo real acumulado.

Poupança

  • A diferença entre o custo amortizado total acumulado e o custo real total acumulado é chamado de poupança acumulada (en: accumulated savings).

  • Ocasionalmente o custo de uma operação vai ser maior que o seu custo amortizado. Neste caso, retiramos a diferença da poupança.

    • Tais operações são denominadas caras (en: expensive).
    • As que tem custo real igual ou inferior ao amortizado são chamadas de baratas (en: cheap).

  • A chave é mostrar que operações caras só ocorrem quando a diferença do custo pode ser paga pela poupança!

Créditos

  • O método do banqueiro associa créditos a cada elemento/posição da estrutura de dados.
  • Quando essas posições forem acessadas, esses créditos pagarão a diferença no custo.

Invariante

  • Todo crédito precisa ser alocado antes de ser usado e nenhum crédito pode ser usado mais de uma vez!

  • Normalmente para usar o método do banqueiro, define-se um invariante que garante que quando uma operação cara ocorrer então, há dinheiro suficiente na poupança para cobrir o custo.

1.5 O método do Banqueiro e a Fila

  • head tem custo amortizado 1 (e real também!)

  • snoc

    • O invariante para a nossa análise é de que cada elemento em r está associado com \(1\) crédito.
    • Quando ocorre um snoc, gastamos um crédito para colocar o elemento em r e outro para deixar associado ao elemento propriamente dito.
      • Assim, uma lista r com \(n\) elementos tem \(n\) créditos associados.
      • O custo amortizado de uma operação snoc é portanto \(2\)
  • tail
    • Se tail não precisar inverter a lista, ele custa 1 crédito
    • Se tail precisar inverter a lista, ele precisará fazer \(n + 1\) passos, onde \(n\) é o tamanho da lista.
      • A poupança neste caso tem \(n\) créditos
      • Após a execução de tail, a poupança estará vazia e tail terá tido um custo amortizado de \(1\) (\(n + 1 - n = 1\))

Logo, como todas as operações têm custo amortizado \(\leq 2\), então qualquer sequência com \(n\) operações terá custo amortizado \(\leq 2n = O(n)\).

Não mostramos diretamente, mas é fácil mostrar que de fato \(\sum_{i=1}^{j} a_i \ge \sum_{i=1}^{j}\) vale.

1.6 Revisitando os Heaps Binomiais

  • Mostramos que a inserção em heaps binomiais leva tempo \(O(\lg n)\).
  • É possível mostrar que a inserção leva tempo \(O(1)\) amortizado
  • Lembre-se do odômetro!
    • O número de árvores no heap é equivalente ao número de \(1\text{s}\) na sua representação em binário
    • Inserção precisa de \(k + 1\) passos onde \(k\) é o número de chamadas a função link.
    • Se mantivermos um crédito por árvore, o custo amortizado de insert (descontados os créditos da poupança) passa a ser O(1).

2 Referências

2.1 Livros

  • [CO]
  • Purely Functional Data Structures
    • Por Chris Okasaki

  • [CLRS]
  • Introduction to Algorithms
    • Por Thomas H. Cormen & Charles E. Leiserson & Ronald L. Rives/t & /Clifford Stein

3 Disclaimer

Estes slides foram preparados para os cursos de Paradigmas de Programação e Desenvolvimento Orientado a Tipos na UFABC.

Este material pode ser usado livremente desde que sejam mantidos, além deste aviso, os créditos aos autores e instituições.

  1. Os método do banqueiro e do físico são equivalentes, mas por motivos de tempo nos concentraremos aqui apenas no método do banqueiro. Caso queira saber mais sobre o método cheque os livros [CO] e [CLRS]. Para a mesma demonstração que fazemos aqui para filas veja o capítulo 5 de [CO]. ↩︎

  2. snoc vem de cons na ordem inversa. Ninguém sabe exatamente quando isso surgiu, mas há papers da década de 70 que já usam essa nomenclatura. ↩︎