Método de potenciales (análisis de amortización)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 7 de abril de 2020; la verificación requiere 1 edición .

El método potencial es uno de los métodos de análisis de depreciación que le permite "suavizar" el impacto de operaciones costosas pero raras en la complejidad computacional total del algoritmo [1] [2] .

Definiciones

En el método de los potenciales, se introduce una función que vincula el estado de la estructura de datos con algún número no negativo. El significado de esta función es que si es el estado actual de la estructura, entonces es un valor que caracteriza la cantidad de trabajo de operaciones "caras", que ya ha sido "pagado" por operaciones más baratas, pero no ha sido producido. Por lo tanto, puede considerarse como un análogo de la energía potencial asociada a un estado dado [1] [2] . Inicialmente, el valor de la función potencial generalmente se establece en cero. $\Fi$ $S$ ${\ estilo de visualización \ Phi (S)}$ ${\ estilo de visualización \ Phi (S)}$

Sea alguna operación separada de la serie, sea el estado de la estructura antes de esta operación, y sea después de ella. Entonces la complejidad amortizada de la operación es $o$ $S_{antes}$ $S_{después}$ $o$

T_{\mathrm {amortizado} }(o)=T_{\mathrm {real} }(o)+\Phi (S_{\mathrm {después} })-\Phi (S_{\mathrm {antes} }).

Relación entre valor depreciado y valor real

El costo total amortizado de una secuencia de operaciones es un límite superior válido para el costo real de esa secuencia de operaciones.

Para una secuencia de operaciones , se puede definir: ${\displaystyle O=o_{1},o_{2},\dots,o_{n))$

Tiempo total amortizado: $T_{\mathrm {amortizado} }(O)=\sum _{i=0}^{n}T_{\mathrm {amortizado} }(o_{i}),$
Tiempo real total: $T_{\mathrm {real} }(O)=\sum _{i=0}^{n}T_{\mathrm {real} }(o_{i}).$

En estas notaciones:

T_{\mathrm {amortizado} }(O)=\sum _{i=1}^{n}\left(T_{\mathrm {real} }(o_{i})+\Phi (S_{ i})-\Phi (S_{i-1})\right)=T_{\mathrm {real} }(O)+\Phi (S_{n})-\Phi (S_{0}),

Así, la secuencia de valores de funciones potenciales forma una suma telescópica , en la que sucesivos valores iniciales y finales de funciones potenciales se anulan entre sí.

Del hecho de que se sigue la desigualdad , como se dijo anteriormente. ${\ estilo de visualización \ Phi (S_ {0}) = 0}$ ${\ estilo de visualización \ Phi (S_ {n}) \ geq 0}$ $T_{\mathrm {real} }(O)\leq T_{\mathrm {amortizado} }(O)$

Ejemplos

Pila con mudanzas masivas

Puede considerar una variante de la pila que admita las siguientes operaciones:

inicializar : crea una pila vacía.
empujar : agregue un solo elemento a la parte superior de la pila, aumentando su tamaño en . $una$
pop(k) - elimina elementos de la parte superior de la pila, donde no exceda el tamaño de la pila actual. $k$ $k$

Una operación pop(k) toma tiempo, mientras que el tiempo total de ejecución se puede analizar usando la siguiente función potencial igual al número de elementos en la pila . Este valor siempre es no negativo, mientras que la operación push trabaja para una constante y aumenta en uno, y la operación pop trabaja para , pero también disminuye la función potencial en , por lo que su tiempo amortizado también es constante. De esto se deduce que el tiempo total de ejecución de cualquier secuencia de operaciones es igual en el peor de los casos. $OK)$ ${\ estilo de visualización \ Phi (S)}$ $S$ $\Fi$ $OK)$ $k$ $metro$ $O(m)$

Contador binario

Otro ejemplo es un contador , implementado como un número binario que admite las siguientes operaciones:

initialize -- crea un contador con valor . ${\ estilo de visualización 0}$
inc : incrementa el valor del contador en . $una$

Para mostrar que el costo amortizado de inc es , considere una función potencial igual al número de bits del contador igual a ( peso de Hamming contador). Como se requiere, dicha función siempre es no negativa e inicialmente es igual a . La operación inc primero invierte el bit menos significativo del contador y luego, si era , repite lo mismo con el siguiente bit hasta que llega a . Si antes había bits individuales al final del registro de bits del contador, será necesario invertir el bit, gastando unidades de tiempo real y reduciendo el potencial en . Así, el coste amortizado de la operación inc es igual y, en consecuencia, el tiempo de ejecución de las operaciones inc es igual a . $O(1)$ $una$ ${\ estilo de visualización 0}$ $una$ ${\ estilo de visualización 0}$ $k$ $k+1$ $k+1$ $k-1$ $2$ $metro$ $O(m)$

Aplicaciones

El método de los potenciales se usa comúnmente para analizar montones de Fibonacci , donde extraer un elemento toma un tiempo logarítmico amortizado, y todas las demás operaciones toman un tiempo constante amortizado [3] . También se puede usar para mostrar que un árbol splay tiene un costo de operaciones amortizado logarítmico [4] .

Notas

↑ 1 2 Goodrich, Michael T. & Tamassia, Roberto (2002), 1.5.1 Técnicas de amortización, diseño de algoritmos: fundamentos, análisis y ejemplos de Internet , Wiley, p. 36–38 .
↑ 1 2 Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. 18.3 Método potencial // Algoritmos: construcción y análisis = Introducción a los algoritmos / Ed. I. V. Krasikova. - 2ª ed. - M. : Williams, 2005. - S. 412-416. — ISBN 5-8459-0857-4 .
↑ Cormen et al., Capítulo 20, "Montones de Fibonacci", págs. 476-497.
↑ Goodrich y Tamassia, Sección 3.4, "Splay Trees", págs. 185-194.