Análisis amortizado

En informática , el análisis amortizado es un método para analizar la complejidad de un algoritmo dado , o cuántos recursos, especialmente tiempo o memoria, requiere su ejecución . La motivación para el análisis amortizado es que observar el tiempo de ejecución en el peor de los casos puede ser demasiado pesimista. En cambio, el análisis amortizado promedia los tiempos de ejecución de las operaciones en una secuencia a lo largo de esa secuencia. ^{[ 1 ]}^{: 306} Como conclusión: "El análisis amortizado es una herramienta útil que complementa otras técnicas como el análisis del peor caso y el análisis del caso promedio ." ^{[ 2 ]}^{: 14}^{[ 3 ]}

Para una operación determinada de un algoritmo, ciertas situaciones (por ejemplo, parametrizaciones de entrada o contenido de la estructura de datos) pueden implicar un costo significativo en recursos, mientras que otras situaciones pueden no ser tan costosas. El análisis amortizado considera tanto las operaciones costosas como las menos costosas en conjunto a lo largo de toda la secuencia de operaciones. Esto puede incluir la consideración de diferentes tipos de entrada, la longitud de la entrada y otros factores que afectan su rendimiento. ^{[ 2 ]}

Historia

El análisis amortizado surgió inicialmente de un método llamado análisis agregado, que ahora se engloba dentro del análisis amortizado. La técnica fue introducida formalmente por primera vez por Robert Tarjan en su artículo de 1985 , «Complejidad computacional amortizada » ^{[ 1 ]} , que abordaba la necesidad de una forma de análisis más útil que los métodos probabilísticos comunes. La amortización se utilizó inicialmente para tipos de algoritmos muy específicos, en particular aquellos que involucran árboles binarios y operaciones de unión . Sin embargo, ahora es omnipresente y se aplica al análisis de muchos otros algoritmos ^{[ 2 ] .}

Método

El análisis amortizado requiere conocer qué secuencias de operaciones son posibles. Esto suele ocurrir con las estructuras de datos , cuyo estado persiste entre operaciones. La idea básica es que una operación en el peor de los casos puede alterar el estado de tal forma que dicho caso no vuelva a ocurrir durante un largo periodo, amortizando así su coste.

Generalmente existen tres métodos para realizar el análisis amortizado: el método agregado, el método contable y el método potencial . Todos ellos proporcionan resultados correctos; la elección del método a utilizar depende de cuál sea el más conveniente para una situación particular. ^{[ 4 ]}

El análisis agregado determina el límite superior T ( n ) del costo total de una secuencia de n operaciones, y luego calcula el costo amortizado como T ( n ) / n . ^{[ 4 ]}
El método contable es una forma de análisis agregado que asigna a cada operación un costo amortizado que puede diferir de su costo real. Las operaciones iniciales tienen un costo amortizado mayor que su costo real, lo que acumula un "crédito" ahorrado que paga las operaciones posteriores con un costo amortizado menor que su costo real. Dado que el crédito comienza en cero, el costo real de una secuencia de operaciones es igual al costo amortizado menos el crédito acumulado. Como el crédito debe ser no negativo, el costo amortizado es un límite superior del costo real. Por lo general, muchas operaciones de corta duración acumulan dicho crédito en pequeños incrementos, mientras que las raras operaciones de larga duración lo reducen drásticamente. ^{[ 4 ]}
El método potencial es una forma del método contable donde el crédito ahorrado se calcula como una función (el "potencial") del estado de la estructura de datos. El costo amortizado es el costo inmediato más la variación del potencial. ^{[ 4 ]}

Ejemplos

Matriz dinámica

Consideremos un array dinámico cuyo tamaño aumenta a medida que se le añaden elementos, como ArrayListen Java o std::vectorC++. Si partimos de un array dinámico de tamaño 4, podríamos añadirle 4 elementos, y cada operación tardaría un tiempo constante . Sin embargo, añadir un quinto elemento a ese array tardaría más, ya que el array tendría que crear un nuevo array de tamaño escalado, copiar los elementos antiguos al nuevo array y luego añadir el nuevo elemento. Las siguientes operaciones de inserción también tardarían un tiempo constante, y la adición posterior requeriría otro escalado lento del tamaño del array.

En general, para un número arbitrario $n$ de inserciones a una matriz de cualquier tamaño inicial, los tiempos de los pasos que escalan la matriz se suman en una serie geométrica a $O(n)$ , mientras que los tiempos constantes para cada empuje restante también se suman a $O(n)$ Por lo tanto, el tiempo promedio por operación de empuje es $O(n)/n=O(1)$ Este razonamiento puede formalizarse y generalizarse a estructuras de datos más complejas mediante análisis amortizado. ^{[ 4 ]}

Cola

Aquí se muestra una implementación en Python de una cola , una estructura de datos FIFO :

clase Cola : """Representa una colección de tipo primero en entrar, primero en salir.""" # Inicializa la cola con dos listas vacías def __init__(self): self.input = [ ] # Almacena los elementos que se encolan self.output = [ ] # Almacena los elementos que se desencolandef enqueue ( self , element ): "" " Agrega un objeto al final de la cola.""" self.input.append ( element ) # Agrega el elemento a la lista de entradadef dequeue ( self ): " ""Elimina y devuelve el objeto al principio de la cola.""" if not self.output: # Si la lista de salida está vacía # Transfiere todos los elementos de la lista de entrada a la lista de salida, invirtiendo el orden while self.input : # Mientras la lista de entrada no esté vacía self.output.append ( self.input.pop ( ) ) # Extrae el último elemento de la lista de entrada y lo agrega a la lista de salidareturn self.output.pop () # Extrae y devuelve el último elemento de la lista de salida .

La operación de encolado simplemente agrega un elemento al array de entrada; esta operación no depende de la longitud de la entrada ni de la salida y, por lo tanto, se ejecuta en tiempo constante.

Sin embargo, la operación de desencolado es más complicada. Si el array de salida ya tiene algunos elementos, entonces desencolado se ejecuta en tiempo constante; de lo contrario, desencolado tarda ⁠ $O(n)$ tiempo para agregar todos los elementos al arreglo de salida desde el arreglo de entrada, donde n es la longitud actual del arreglo de entrada. Después de copiar n elementos de la entrada, podemos realizar n operaciones de desencolado, cada una tomando un tiempo constante, antes de que el arreglo de salida esté vacío nuevamente. Por lo tanto, podemos realizar una secuencia de n operaciones de desencolado en solo $O(n)$ tiempo , lo que implica que el tiempo amortizado de cada operación de desencolado es $O(1)$ ⁠ .^{[ 5 ]}

Alternativamente, podemos cargar el costo de copiar cualquier elemento del array de entrada al array de salida a la operación de encolado anterior para ese elemento. Este esquema de carga duplica el tiempo amortizado para encolar pero reduce el tiempo amortizado para desencolar a ⁠ $O(1)$ ⁠ .

Uso común

En el uso común, un "algoritmo amortizado" es aquel que, según un análisis amortizado, ha demostrado tener un buen rendimiento.
Los algoritmos en línea suelen utilizar análisis amortizado.

Referencias

1 2 Tarjan, Robert Endre (abril de 1985). "Complejidad computacional amortizada" (PDF) . SIAM Journal on Algebraic and Discrete Methods . 6 (2): 306– 318. doi : 10.1137/0606031 . Archivado (PDF) del original el 26 de febrero de 2015. Recuperado el 9 de junio de 2024 .
1 2 3 Rebecca Fiebrink (2007), Análisis amortizado explicado (PDF) , archivado del original (PDF) el 20 de octubre de 2013 , recuperado el 3 de mayo de 2011
↑ "Clase 18: Algoritmos Amortizados" . CS312 - Estructuras de Datos y Programación Funcional . Universidad de Cornell. 2006. [El análisis amortizado] es diferente de lo que comúnmente se conoce como análisis del caso promedio, porque el análisis amortizado no hace ninguna suposición sobre la distribución de los valores de los datos, mientras que el análisis del caso promedio supone que los datos no son "malos" (por ejemplo, algunos algoritmos de ordenación funcionan bien "en promedio" para todos los órdenes de entrada, pero muy mal para ciertos órdenes de entrada). Es decir, el análisis amortizado es un análisis del peor caso, pero para una secuencia de operaciones, en lugar de para operaciones individuales.
1 2 3 4 5 Kozen, Dexter (Primavera de 2011). "CS 3110 Conferencia 20: Análisis Amortizado" . Universidad de Cornell . Recuperado el 14 de marzo de 2015 .
↑ Grossman, Dan. "CSE332: Abstracciones de datos" (PDF) . cs.washington.edu . Consultado el 14 de marzo de 2015 .

Literatura

"Lección 7: Análisis amortizado" (PDF) . Universidad Carnegie Mellon . Consultado el 14 de marzo de 2015 .
Allan Borodin y Ran El-Yaniv (1998). Computación en línea y análisis competitivo . págs. 20, 141.

[tarjan-1] 1 2 Tarjan, Robert Endre (abril de 1985). "Complejidad computacional amortizada" (PDF) . SIAM Journal on Algebraic and Discrete Methods . 6 (2): 306– 318. doi : 10.1137/0606031 . Archivado (PDF) del original el 26 de febrero de 2015. Recuperado el 9 de junio de 2024 .

[fiebrink-2] 1 2 3 Rebecca Fiebrink (2007), Análisis amortizado explicado (PDF) , archivado del original (PDF) el 20 de octubre de 2013 , recuperado el 3 de mayo de 2011

[3] "Clase 18: Algoritmos Amortizados" . CS312 - Estructuras de Datos y Programación Funcional . Universidad de Cornell. 2006. [El análisis amortizado] es diferente de lo que comúnmente se conoce como análisis del caso promedio, porque el análisis amortizado no hace ninguna suposición sobre la distribución de los valores de los datos, mientras que el análisis del caso promedio supone que los datos no son "malos" (por ejemplo, algunos algoritmos de ordenación funcionan bien "en promedio" para todos los órdenes de entrada, pero muy mal para ciertos órdenes de entrada). Es decir, el análisis amortizado es un análisis del peor caso, pero para una secuencia de operaciones, en lugar de para operaciones individuales.

[Lecture_20-4] 1 2 3 4 5 Kozen, Dexter (Primavera de 2011). "CS 3110 Conferencia 20: Análisis Amortizado" . Universidad de Cornell . Recuperado el 14 de marzo de 2015 .

[Grossman-5] Grossman, Dan. "CSE332: Abstracciones de datos" (PDF) . cs.washington.edu . Consultado el 14 de marzo de 2015 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]