En informática , el análisis amortizado es un método para analizar la complejidad de un algoritmo determinado , o la cantidad de un recurso, especialmente tiempo o memoria, que se necesita para ejecutarlo . La motivación para el análisis amortizado es que mirar el tiempo de ejecución del 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 de los casos y el análisis del caso promedio ". [2] : 14
Para una operación dada de un algoritmo, ciertas situaciones (por ejemplo, parametrizaciones de entrada o contenidos 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 contabilización de diferentes tipos de entrada, la longitud de la entrada y otros factores que afectan su rendimiento. [2]
El análisis amortizado surgió inicialmente de un método llamado análisis agregado, que ahora está incluido en el análisis amortizado. La técnica fue introducida formalmente por primera vez por Robert Tarjan en su artículo de 1985 Amortized Computational Complexity [1] , que abordaba la necesidad de una forma de análisis más útil que los métodos probabilísticos comunes utilizados. La amortización se utilizó inicialmente para tipos muy específicos de algoritmos, en particular aquellos que involucraban árboles binarios y operaciones de unión . Sin embargo, ahora es omnipresente y entra en juego también al analizar muchos otros algoritmos. [2]
El análisis amortizado requiere saber qué series de operaciones son posibles. Esto es lo que ocurre más comúnmente con las estructuras de datos , que tienen un estado que persiste entre operaciones. La idea básica es que una operación en el peor de los casos puede alterar el estado de tal manera que el peor de los casos no pueda volver a ocurrir durante mucho tiempo, "amortizando" así su costo.
En general, 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 dan respuestas correctas; la elección de cuál utilizar depende de cuál sea más conveniente para una situación particular. [3]
Consideremos una matriz dinámica que crece en tamaño a medida que se le agregan más elementos, como ArrayListen Java o std::vectoren C++. Si comenzamos con una matriz dinámica de tamaño 4, podríamos insertar 4 elementos en ella, y cada operación tomaría un tiempo constante . Sin embargo, insertar un quinto elemento en esa matriz tomaría más tiempo ya que la matriz tendría que crear una nueva matriz del doble del tamaño actual (8), copiar los elementos antiguos en la nueva matriz y luego agregar el nuevo elemento. Las siguientes tres operaciones de inserción tomarían un tiempo constante de manera similar, y luego la adición posterior requeriría otra duplicación lenta del tamaño de la matriz.
En general, para una cantidad arbitraria de operaciones de inserción en una matriz de cualquier tamaño inicial, los tiempos de los pasos que duplican la matriz se suman en una serie geométrica a , mientras que los tiempos constantes para cada operación de inserción restante también se suman a . Por lo tanto, el tiempo promedio por operación de inserción es . Este razonamiento se puede formalizar y generalizar a estructuras de datos más complicadas mediante el uso de análisis amortizado. [3]
Se muestra una implementación en Python3 de una cola , una estructura de datos FIFO :
clase Queue : # Inicializa la cola con dos listas vacías def __init__ ( self ): self.input = [] # Almacena elementos que están en cola self.output = [ ] # Almacena elementos que están fuera de cola def enqueue ( self , element ): self.input.append ( element ) # Agrega el elemento a la lista de entrada def dequeue ( self ): if not self.output : # Si la lista de salida está vacía # Transferir 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 ( )) # Extraer el último elemento de la lista de entrada y agregarlo a la lista de salida return self . output . pop () # Extrae y devuelve el último elemento de la lista de salidaLa operación de poner en cola simplemente inserta un elemento en la matriz de entrada; esta operación no depende de las longitudes de la entrada ni de la salida y, por lo tanto, se ejecuta en tiempo constante.
Sin embargo, la operación de deshacer cola es más complicada. Si la matriz de salida ya tiene algunos elementos, entonces la deshacer cola se ejecuta en tiempo constante; de lo contrario, la deshacer cola tarda tiempo en agregar todos los elementos a la matriz de salida desde la matriz de entrada, donde n es la longitud actual de la matriz de entrada. Después de copiar n elementos desde la entrada, podemos realizar n operaciones de deshacer cola, cada una de las cuales toma un tiempo constante, antes de que la matriz de salida vuelva a estar vacía. Por lo tanto, podemos realizar una secuencia de n operaciones de deshacer cola en solo tiempo, lo que implica que el tiempo amortizado de cada operación de deshacer cola es . [4]
Como alternativa, podemos cobrar el costo de copiar cualquier elemento de la matriz de entrada a la matriz de salida a la operación de encolado anterior para ese elemento. Este esquema de cobro duplica el tiempo amortizado para encolar, pero reduce el tiempo amortizado para sacar de la cola a .
