Método potencial

En la teoría de la complejidad computacional , el método potencial es un método utilizado para analizar la complejidad amortizada de tiempo y espacio de una estructura de datos , una medida de su rendimiento sobre secuencias de operaciones que suaviza el costo de las operaciones poco frecuentes pero costosas. ^{[ 1 ]}^{[ 2 ]}

Definición de tiempo amortizado

En el método potencial, se elige una función Φ que asigna 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, Φ( S ) puede interpretarse como el cálculo de la cantidad de energía potencial almacenada en ese estado. ^{[ 1 ]}^{[ 2 ]} El valor potencial previo a la operación de inicialización de una estructura de datos se define como cero. Alternativamente, Φ( S ) puede interpretarse como 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 sobre alguna estructura de datos, donde S _antes denota el estado de la estructura de datos antes de la operación o y S _después denota su estado después de que la operación o se haya completado. Una vez que se ha elegido Φ , el tiempo amortizado para la operación o se define como:

T_{\mathrm {amortizado} }(o)=T_{\mathrm {actual} }(o)+C\cdot (\Phi (S_{\mathrm {después} })-\Phi (S_{\mathrm {antes} })),

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 empleado por 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, por lo que la constante C generalmente se omite.

Relación entre el tiempo amortizado y el tiempo real

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

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

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

Entonces:

T_{\mathrm {amortizado} }(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, excepto los valores inicial y final de la función potencial, se cancelan por pares. Reordenando esto, obtenemos:

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

Desde $\Phi (S_{0})=0$ y $\Phi (S_{n})\geq 0$ , $T_{\mathrm {actual} }(O)\leq T_{\mathrm {amortizado} }(O)$ Por lo tanto, el tiempo amortizado puede utilizarse para proporcionar un límite superior preciso del tiempo real de una secuencia de operaciones, aunque el tiempo amortizado de una operación individual pueda variar ampliamente con respecto a su tiempo real.

Análisis amortizado de los peores escenarios de entrada

Normalmente, el análisis amortizado se utiliza en combinación con una suposición del peor caso sobre la secuencia de entrada. Con esta suposición, si X es un tipo de operación que puede realizar la estructura de datos, y n es un 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 en estructuras de datos de tamaño n y 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 necesario para realizar una secuencia de operaciones puede estimarse multiplicando el tiempo amortizado de cada tipo de operación en la secuencia por el número de operaciones de ese tipo.

Ejemplos

Matriz dinámica

Un array dinámico es una estructura de datos para mantener un array de elementos, permitiendo tanto el acceso aleatorio a posiciones dentro del array como la posibilidad de incrementar su tamaño en uno. Está disponible en Java como el tipo "ArrayList" y en Python como el tipo "list".

Un arreglo dinámico puede implementarse mediante una estructura de datos que consiste en un arreglo A de elementos, de cierta longitud N , junto con un número n ≤ N que representa las posiciones dentro del arreglo que se han utilizado hasta el momento. Con esta estructura, los accesos aleatorios al arreglo dinámico pueden implementarse accediendo a la misma celda del arreglo interno A , y cuando n < N, una operación que aumenta el tamaño del arreglo dinámico puede implementarse simplemente incrementando n . Sin embargo, cuando n = N , es necesario redimensionar A , y una estrategia común para hacerlo es duplicar su tamaño, reemplazando A por un nuevo arreglo de longitud 2n . ^[³^]

Esta estructura puede analizarse utilizando la función potencial:

Φ = 2 n − N

Dado que la estrategia de redimensionamiento siempre hace que A esté al menos medio lleno, esta función potencial siempre es no negativa, como se deseaba.

Cuando una operación de aumento de tamaño no conlleva una operación de redimensionamiento, Φ aumenta en 2, una constante. Por lo 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 redimensionamiento, el valor potencial de Φ disminuye a cero después del redimensionamiento. Asignar un nuevo arreglo interno A y copiar todos los valores del arreglo interno antiguo al nuevo toma un tiempo real de O( n ), pero (con una elección apropiada de la constante de proporcionalidad C ) esto se cancela completamente por la disminución de la función potencial, dejando nuevamente un tiempo amortizado total constante para la operación.

Las demás operaciones de la estructura de datos (leer y escribir celdas de la matriz sin cambiar el tamaño de la matriz) no provocan que la función potencial cambie y tienen el mismo tiempo amortizado constante que su tiempo real. ^{[ 2 ]}

Por lo tanto, con esta elección de estrategia de redimensionamiento y función potencial, el método potencial muestra que todas las operaciones de matriz dinámica toman un tiempo amortizado constante. Combinando esto con la desigualdad que relaciona el tiempo amortizado y el tiempo real en secuencias de operaciones, se demuestra que cualquier secuencia de n operaciones de matriz dinámica toma un tiempo real de O( n ) en el peor de los casos, a pesar de que algunas de las operaciones individuales pueden tomar un tiempo lineal. ^{[ 2 ]}

Cuando el arreglo dinámico incluye operaciones que disminuyen el tamaño del arreglo además de aumentarlo, la función potencial debe modificarse para evitar que se vuelva negativa. Una forma de hacerlo es reemplazar la fórmula anterior para Φ por su valor absoluto .

pila multipop

Consideremos una pila que admita las siguientes operaciones:

Inicializar: crear una pila vacía.
Push: agrega un solo elemento en la parte superior de la pila, aumentando el tamaño de la pila en 1.
Pop( k ) - elimina k elementos de la parte superior de la pila, donde k no es mayor que el tamaño actual de la pila.

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

Esta estructura puede analizarse utilizando la función potencial:

Φ = número de elementos en la pila

Este número siempre es no negativo, como se requiere.

Una operación de empuje requiere un tiempo constante e incrementa Φ en 1, por lo que su tiempo amortizado es constante.

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

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

Contador binario

Consideremos un contador representado como un número binario que admite las siguientes operaciones:

Inicializar: crea un contador con valor 0.
Inc: suma 1 al contador.
Lectura: devuelve el valor actual del contador.

Para este ejemplo, no utilizamos el modelo de máquina transdicotómica , sino que requerimos una unidad de tiempo por cada operación de bit en el incremento. Queremos demostrar que Inc requiere un tiempo amortizado de O(1).

Esta estructura puede analizarse utilizando la función potencial:

Φ = número de bits iguales a 1 = peso de Hamming (contador)

Este número siempre es no negativo y comienza con 0, como se requiere.

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

Aplicaciones

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

Referencias

1 2 3 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, pp. 36– 38 .
1 2 3 4 5 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.
↑ 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.
↑ Cormen et al., Capítulo 20, "Montículos de Fibonacci", págs. 476–497.
↑ Goodrich y Tamassia, Sección 3.4, "Árboles ramificados", págs. 185–194.

[gt-ad-1] 1 2 3 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, pp. 36– 38 .

[clrs-2] 1 2 3 4 5 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, "Montículos de Fibonacci", págs. 476–497.

[5] Goodrich y Tamassia, Sección 3.4, "Árboles ramificados", págs. 185–194.

[ 1 ]

[ 2 ]

[

[ 4 ]

[ 5 ]

Definición de tiempo amortizado

Relación entre el tiempo amortizado y el tiempo real

Análisis amortizado de los peores escenarios de entrada

Ejemplos

Matriz dinámica

pila multipop

Contador binario

Aplicaciones

Referencias

Articulos relacionados