Método potencial

En la teoría de la complejidad computacional , el método potencial es un método utilizado para analizar la complejidad temporal y espacial amortizada de una estructura de datos , una medida de su desempeño en secuencias de operaciones que suaviza el costo de operaciones poco frecuentes pero costosas. ^{[1] [2]}

Definición de tiempo amortizado

En el método potencial, se elige una función Φ que mapea estados de la estructura de datos a números no negativos. Si S es un estado de la estructura de datos, Φ ( S ) representa el trabajo que se ha contabilizado ("pagado") en el análisis amortizado pero que aún no se ha realizado. Por lo tanto, se puede pensar que Φ ( S ) calcula la cantidad de energía potencial almacenada en ese estado. ^{[1] [2]} El valor potencial antes de la operación de inicialización de una estructura de datos se define como cero. Alternativamente, se puede pensar que Φ ( S ) representa la cantidad de desorden en el estado S o su distancia de un estado ideal.

Sea o cualquier operación individual dentro de una secuencia de operaciones en alguna estructura de datos, con S _{antes de} denotar el estado de la estructura de datos antes de la operación o y S _{después de} denotar su estado después de que la operación o se haya completado. Una vez elegido Φ, el tiempo amortizado para la operación o se define como

${\displaystyle T_{\mathrm {amortized} }(o)=T_{\mathrm {actual} }(o)+C\cdot (\Phi (S_{\mathrm {after} })-\Phi (S_{\mathrm {before} })),}$

donde C es una constante de proporcionalidad no negativa (en unidades de tiempo) que debe permanecer fija durante todo el análisis. Es decir, el tiempo amortizado se define como el tiempo real que toma la operación más C multiplicado por la diferencia de potencial causada por la operación. ^{[1] [2]}

Al estudiar la complejidad computacional asintótica utilizando la notación O grande , los factores constantes son irrelevantes y, por lo tanto, la constante C generalmente se omite.

Relación entre tiempo amortizado y real

A pesar de su apariencia artificial, el tiempo total amortizado de una secuencia de operaciones proporciona un límite superior válido en el tiempo real para la misma secuencia de operaciones.

Para cualquier secuencia de operaciones , defina:${\displaystyle O=o_{1},o_{2},\dots ,o_{n}}$

• El tiempo total amortizado: ${\displaystyle T_{\mathrm {amortized} }(O)=\sum _{i=1}^{n}T_{\mathrm {amortized} }(o_{i}),}$
• El tiempo real total: ${\displaystyle T_{\mathrm {actual} }(O)=\sum _{i=1}^{n}T_{\mathrm {actual} }(o_{i}).}$

Luego:

${\displaystyle T_{\mathrm {amortized} }(O)=\sum _{i=1}^{n}\left(T_{\mathrm {actual} }(o_{i})+C\cdot (\Phi (S_{i})-\Phi (S_{i-1}))\right)=T_{\mathrm {actual} }(O)+C\cdot (\Phi (S_{n})-\Phi (S_{0})),}$

donde la secuencia de valores de la función potencial forma una serie telescópica en la que todos los términos distintos de los valores de la función potencial inicial y final se cancelan en pares. Reordenando esto, obtenemos:

${\displaystyle T_{\mathrm {actual} }(O)=T_{\mathrm {amortized} }(O)-C\cdot (\Phi (S_{n})-\Phi (S_{0})).}$

Desde y , entonces, el tiempo amortizado se puede usar para proporcionar un límite superior preciso sobre el tiempo real de una secuencia de operaciones, aunque el tiempo amortizado para una operación individual puede variar ampliamente de su tiempo real.${\displaystyle \Phi (S_{0})=0}$${\displaystyle \Phi (S_{n})\geq 0}$${\displaystyle T_{\mathrm {actual} }(O)\leq T_{\mathrm {amortized} }(O)}$

Análisis amortizado de las entradas del peor de los casos

Por lo general, el análisis amortizado se utiliza en combinación con el supuesto del peor de los casos sobre la secuencia de entrada. Con esta suposición, si X es un tipo de operación que puede ser realizada por la estructura de datos, yn es un número entero que define el tamaño de la estructura de datos dada (por ejemplo, el número de elementos que contiene), entonces el tiempo amortizado para operaciones de tipo X se define como el máximo, entre todas las secuencias posibles de operaciones sobre estructuras de datos de tamaño ny todas las operaciones o _i de tipo X dentro de la secuencia, del tiempo amortizado para la operación o _i .

Con esta definición, el tiempo para realizar una secuencia de operaciones puede estimarse multiplicando el tiempo amortizado para cada tipo de operación en la secuencia por el número de operaciones de ese tipo.

Ejemplos de

Matriz dinámica

Una matriz dinámica es una estructura de datos para mantener una matriz de elementos, lo que permite tanto el acceso aleatorio a las posiciones dentro de la matriz como la capacidad de aumentar el tamaño de la matriz en uno. Está disponible en Java como el tipo "ArrayList" y en Python como el tipo "list".

Una matriz dinámica puede implementarse mediante una estructura de datos que consta de una matriz A de elementos, de alguna longitud N , junto con un número n  ≤  N que representa las posiciones dentro de la matriz que se han utilizado hasta ahora. Con esta estructura, se pueden implementar accesos aleatorios a la matriz dinámica accediendo a la misma celda de la matriz interna A , y cuando n  <  N se puede implementar una operación que aumenta el tamaño de la matriz dinámica simplemente incrementando  n . Sin embargo, cuando n  =  N , es necesario cambiar el tamaño de A, y una estrategia común para hacerlo es duplicar su tamaño, reemplazando A por una nueva matriz de longitud 2 n . ^[3]

Esta estructura se puede analizar utilizando la función potencial:

Φ = 2 n  -  N

Dado que la estrategia de cambio de tamaño siempre hace que A esté al menos medio lleno, esta función potencial siempre es no negativa, como se desea.

Cuando una operación de aumento de tamaño no conduce a una operación de cambio de tamaño, Φ aumenta en 2, una constante. Por tanto, el tiempo real constante de la operación y el aumento constante del potencial se combinan para dar un tiempo amortizado constante para una operación de este tipo.

Sin embargo, cuando una operación de aumento de tamaño provoca un cambio de tamaño, el valor potencial de n disminuye a cero después del cambio de tamaño. Asignar una nueva matriz interna A y copiar todos los valores de la matriz interna anterior a la nueva toma O ( n ) tiempo real, pero (con una elección adecuada de la constante de proporcionalidad C ) esto se cancela por completo por la disminución de la función potencial, dejando nuevamente un tiempo total amortizado constante para la operación.

Las otras operaciones de la estructura de datos (leer y escribir celdas de la matriz sin cambiar el tamaño de la matriz) no hacen que la función potencial cambie y tengan el mismo tiempo amortizado constante que su tiempo real. ^[2]

Por lo tanto, con esta elección de estrategia de cambio de tamaño y función potencial, el método potencial muestra que todas las operaciones de matriz dinámica toman un tiempo de amortización constante. Combinando esto con la desigualdad que relaciona el tiempo amortizado y el tiempo real sobre secuencias de operaciones, esto muestra que cualquier secuencia de n operaciones de matriz dinámica toma O ( n ) tiempo real en el peor de los casos, a pesar del hecho de que algunas de las operaciones individuales pueden tomar por sí mismas. una cantidad lineal de tiempo. ^[2]

Cuando la matriz dinámica incluye operaciones que disminuyen el tamaño de la matriz y lo aumentan, la función potencial debe modificarse para evitar que se vuelva negativa. Una forma de hacer esto es reemplazar la fórmula anterior para Φ por su valor absoluto .

Pila de varios pop

Considere una pila que admita las siguientes operaciones:

• Inicializar: crea una pila vacía.
• Empujar: agregue un solo elemento en la parte superior de la pila, agrandando la pila en 1.
• Pop ( k ): elimina k elementos de la parte superior de la pila, donde k no es más que el tamaño de la pila actual

Pop ( k ) requiere O ( k ) tiempo, pero deseamos mostrar que todas las operaciones toman O (1) tiempo amortizado.

Esta estructura se puede analizar utilizando la función potencial:

Φ = número-de-elementos-en-pila

Este número siempre es no negativo, según sea necesario.

Una operación Push toma un tiempo constante y aumenta Φ en 1, por lo que su tiempo amortizado es constante.

Una operación Pop toma tiempo O ( k ) pero también reduce Φ en k , por lo que su tiempo amortizado también es constante.

Esto prueba que cualquier secuencia de m operaciones toma O ( m ) tiempo real en el peor de los casos.

Contador binario

Considere un contador representado como un número binario y que admita las siguientes operaciones:

• Inicializar: crea un contador con valor 0.
• Inc: agrega 1 al contador.
• Leer: devuelve el valor actual del contador.

Para este ejemplo, estamos no utilizamos el modelo de máquina transdichotomous , sino que requieren una unidad de tiempo por cada operación de bit en el incremento. Deseamos mostrar que Inc toma O (1) tiempo amortizado.

Esta estructura se puede analizar utilizando la función potencial:

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

Este número siempre es no negativo y comienza con 0, según sea necesario.

Una operación Inc invierte el bit menos significativo . Luego, si el LSB se invirtió de 1 a 0, el siguiente bit también se invierte. Esto continúa hasta que finalmente se cambia un bit de 0 a 1, momento en el que se detiene el cambio. Si el contador termina inicialmente en k 1 bits, invertimos un total de k +1 bits, tomando el tiempo real k +1 y reduciendo el potencial en k −1, por lo que el tiempo amortizado es 2. Por lo tanto, el tiempo real para ejecutar m Inc operaciones es O ( m ).

Aplicaciones

El método de función potencial se usa comúnmente para analizar montones de Fibonacci , una forma de cola de prioridad en la que eliminar un elemento requiere un tiempo de amortización logarítmica y todas las demás operaciones toman un tiempo de amortización constante. ^[4] También se puede utilizar para analizar splay trees , una forma autoajustable de árbol de búsqueda binaria con tiempo amortizado logarítmico por operación. ^[5]

Referencias

1. 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ágs. 36–38.
2. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. "17.3 El método potencial". Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. págs. 412–416. ISBN 0-262-03293-7.
3. Goodrich y Tamassia, 1.5.2 Análisis de una implementación de matriz extensible, págs. 139-141; Cormen et al., 17.4 Tablas dinámicas, págs. 416–424.
4. Cormen et al., Capítulo 20, "Montones de Fibonacci", págs. 476–497.
5. Goodrich y Tamassia, sección 3.4, "Splay Trees", págs. 185-194.