Método potencial - Potential method

Na teoria da complexidade computacional , o método potencial é um método usado para analisar o tempo amortizado e a complexidade espacial de uma estrutura de dados , uma medida de seu desempenho em sequências de operações que suaviza o custo de operações infrequentes, mas caras.

Definição de tempo amortizado

No método do potencial, é escolhida uma função que mapeia estados da estrutura de dados para números não negativos. Se S for um estado da estrutura de dados, Φ ( S ) representa o trabalho que foi contabilizado ("pago") na análise amortizada, mas ainda não realizado. Assim, Φ ( S ) pode ser pensado como calculando a quantidade de energia potencial armazenada naquele estado. O valor potencial antes da operação de inicialização de uma estrutura de dados é definido como zero. Alternativamente, Φ ( S ) pode ser pensado como representando a quantidade de desordem no estado S ou sua distância de um estado ideal.

Deixe o ser qualquer operação numa sequência de operações em alguma estrutura de dados, com S _antes denotando o estado da estrutura de dados antes da operação O e S _após denotando seu estado após operação o completou. Uma vez que Φ tenha sido escolhido, o tempo amortizado para a operação o é definido como sendo

${\ displaystyle T _ {\ mathrm {amortizado}} (o) = T _ {\ mathrm {atual}} (o) + C \ cdot (\ Phi (S _ {\ mathrm {depois}}) - \ Phi (S _ {\ mathrm {antes}})),}$

onde C é uma constante não negativa de proporcionalidade (em unidades de tempo) que deve permanecer fixa ao longo da análise. Ou seja, o tempo amortizado é definido como o tempo real levado pela operação mais C vezes a diferença de potencial causada pela operação.

Ao estudar a complexidade computacional assintótica usando a notação grande O , os fatores constantes são irrelevantes e, portanto, a constante C geralmente é omitida.

Relação entre o tempo amortizado e real

Apesar de sua aparência artificial, o tempo amortizado total de uma sequência de operações fornece um limite superior válido no tempo real para a mesma sequência de operações.

Para qualquer sequência de operações , defina: ${\ displaystyle O = o_ {1}, o_ {2}, \ dots, o_ {n}}$

• O tempo total amortizado: ${\ displaystyle T _ {\ mathrm {amortizado}} (O) = \ sum _ {i = 1} ^ {n} T _ {\ mathrm {amortizado}} (o_ {i}),}$
• O tempo real total: ${\ displaystyle T _ {\ mathrm {atual}} (O) = \ sum _ {i = 1} ^ {n} T _ {\ mathrm {atual}} (o_ {i}).}$

Então:

${\ displaystyle T _ {\ mathrm {amortizado}} (O) = \ sum _ {i = 1} ^ {n} \ left (T _ {\ mathrm {atual}} (o_ {i}) + C \ cdot (\ Phi (S_ {i}) - \ Phi (S_ {i-1})) \ direita) = T _ {\ mathrm {atual}} (O) + C \ cdot (\ Phi (S_ {n}) - \ Phi (S_ {0})),}$

onde a sequência de valores da função potencial forma uma série telescópica na qual todos os termos, exceto os valores da função potencial inicial e final, se cancelam aos pares. Reorganizando isso, obtemos:

${\ displaystyle T _ {\ mathrm {atual}} (O) = T _ {\ mathrm {amortizado}} (O) -C \ cdot (\ Phi (S_ {n}) - \ Phi (S_ {0})). }$

Desde e , portanto, o tempo amortizado pode ser usado para fornecer um limite superior preciso no tempo real de uma sequência de operações, mesmo que o tempo amortizado para uma operação individual possa variar amplamente de seu tempo real. ${\ displaystyle \ Phi (S_ {0}) = 0}$${\ displaystyle \ Phi (S_ {n}) \ geq 0}$${\ displaystyle T _ {\ mathrm {atual}} (O) \ leq T _ {\ mathrm {amortizado}} (O)}$

Análise amortizada de entradas de pior caso

Normalmente, a análise amortizada é usada em combinação com a hipótese de pior caso sobre a sequência de entrada. Com essa suposição, se X é um tipo de operação que pode ser realizada pela estrutura de dados e n é um número inteiro que define o tamanho da estrutura de dados dada (por exemplo, o número de itens que ela contém), então o tempo amortizado para operações de tipo X é definido como sendo a máxima, entre todas as sequências possíveis de operações em estruturas de tamanho de dados n e todas as operações o _i de tipo X dentro da sequência, do tempo para a operação amortizado o _i .

Com essa definição, o tempo para realizar uma sequência de operações pode ser estimado multiplicando o tempo amortizado para cada tipo de operação na sequência pelo número de operações desse tipo.

Exemplos

Array dinâmico

Uma matriz dinâmica é uma estrutura de dados para manter uma matriz de itens, permitindo o acesso aleatório às posições dentro da matriz e a capacidade de aumentar o tamanho da matriz em um. Ele está disponível em Java como o tipo "ArrayList" e em Python como o tipo "lista".

Uma matriz dinâmica pode ser implementada por uma estrutura de dados que consiste em uma matriz A de itens, de algum comprimento N , juntamente com um número n  ≤  N representando as posições dentro da matriz que foram usadas até agora. Com esta estrutura, os acessos aleatórios ao array dinâmico podem ser implementados acessando a mesma célula do array interno A , e quando n  <  N uma operação que aumenta o tamanho do array dinâmico pode ser implementada simplesmente incrementando  n . No entanto, quando n  =  N , é necessário redimensionar A , e uma estratégia comum para isso é dobrar seu tamanho, substituindo A por um novo array de comprimento 2 n .

Esta estrutura pode ser analisada usando a função potencial:

Φ = 2 n  -  N

Visto que a estratégia de redimensionamento sempre faz com que A esteja pelo menos meio cheio, esta função potencial é sempre não negativa, conforme desejado.

Quando uma operação de aumento de tamanho não leva a uma operação de redimensionamento, Φ aumenta em 2, uma constante. Portanto, o tempo real constante da operação e o aumento constante no potencial combinam-se para dar um tempo amortizado constante para uma operação desse tipo.

No entanto, quando uma operação de aumento de tamanho causa um redimensionamento, o valor potencial de n diminui para zero após o redimensionamento. Alocar uma nova matriz interna A e copiar todos os valores da antiga matriz interna para a nova leva O ( n ) tempo real, mas (com uma escolha apropriada da constante de proporcionalidade C ) isso é totalmente cancelado pela diminuição em a função potencial, deixando novamente um tempo amortizado total constante para a operação.

As outras operações da estrutura de dados (ler e escrever células do array sem alterar o tamanho do array) não fazem com que a função potencial mude e têm o mesmo tempo amortizado constante que seu tempo real.

Portanto, com esta escolha de estratégia de redimensionamento e função potencial, o método potencial mostra que todas as operações de matriz dinâmica levam um tempo amortizado constante. Combinando isso com a desigualdade que relaciona o tempo amortizado e o tempo real ao longo de sequências de operações, isso mostra que qualquer sequência de n operações de matriz dinâmica leva O ( n ) tempo real no pior caso, apesar do fato de que algumas das operações individuais podem levar uma quantidade linear de tempo.

Quando a matriz dinâmica inclui operações que diminuem o tamanho da matriz, bem como aumentam-no, a função potencial deve ser modificada para evitar que se torne negativa. Uma maneira de fazer isso é substituir a fórmula acima para Φ por seu valor absoluto .

Pilha Multi-Pop

Considere uma pilha que suporte as seguintes operações:

• Inicializar - cria uma pilha vazia.
• Empurrar - adiciona um único elemento no topo da pilha, aumentando a pilha em 1.
• Pop ( k ) - remove k elementos do topo da pilha, onde k não é mais do que o tamanho da pilha atual

Pop ( k ) requer tempo O ( k ), mas queremos mostrar que todas as operações levam tempo O (1) amortizado.

Esta estrutura pode ser analisada usando a função potencial:

Φ = número de elementos na pilha

Este número é sempre não negativo, conforme necessário.

Uma operação Push leva um tempo constante e aumenta Φ em 1, portanto, seu tempo amortizado é constante.

Uma operação Pop leva tempo O ( k ), mas também reduz Φ por k , então seu tempo amortizado também é constante.

Isso prova que qualquer sequência de m operações leva O ( m ) tempo real no pior caso.

Contador binário

Considere um contador representado como um número binário e que suporte as seguintes operações:

• Inicializar: crie um contador com valor 0.
• Inc: adicione 1 ao contador.
• Ler: retorna o valor do contador atual.

Para este exemplo, estamos não utilizar o modelo de máquina transdichotomous , mas em vez disso requerem uma unidade de tempo por operação bit no incremento. Queremos mostrar que Inc leva O (1) tempo amortizado.

Esta estrutura pode ser analisada usando a função potencial:

Φ = número-de-bits-igual-a-1 = peso hamming (contador)

Esse número é sempre não negativo e começa com 0, conforme necessário.

Uma operação Inc inverte o bit menos significativo . Então, se o LSB foi invertido de 1 para 0, o próximo bit também é invertido. Isso continua até que finalmente um bit é invertido de 0 para 1, ponto no qual a inversão para. Se o contador termina inicialmente em k 1 bits, invertemos um total de k +1 bits, tomando o tempo real k +1 e reduzindo o potencial em k −1, então o tempo amortizado é 2. Portanto, o tempo real para executar m Operações Inc é O ( m ).

Formulários

O método da função potencial é comumente usado para analisar pilhas de Fibonacci , uma forma de fila de prioridade em que a remoção de um item leva um tempo amortizado logarítmico e todas as outras operações levam um tempo amortizado constante. Também pode ser usado para analisar árvores splay , uma forma autoajustável de árvore de pesquisa binária com tempo amortizado logarítmico por operação.

Referências