En informática , el análisis amortizado es un método para analizar la complejidad de un algoritmo determinado , o cuánto recurso, especialmente tiempo o memoria, se necesita para ejecutarse . La motivación para el análisis amortizado es que mirar 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 sobre 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 del caso promedio ". [2] : 14
Para una operación dada de un algoritmo, ciertas situaciones (por ejemplo, parametrizaciones de entrada o contenidos de estructuras 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 juntas durante toda la secuencia de operaciones. Esto puede incluir tener en cuenta diferentes tipos de insumos, su longitud y otros factores que afectan su desempeño. [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 de algoritmos muy específicos, particularmente aquellos que involucran árboles binarios y operaciones de unión . Sin embargo, ahora es omnipresente y también entra en juego al analizar muchos otros algoritmos. [2]
El análisis amortizado requiere conocer qué series de operaciones son posibles. Este suele ser el caso de 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 manera que el peor de los casos no pueda volver a ocurrir durante mucho tiempo, "amortizando" así su costo.
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 estos dan respuestas correctas; la elección de cuál utilizar depende de cuál es más conveniente para una situación particular. [3]
Considere una matriz dinámica que crece en tamaño a medida que se le agregan más elementos, como ArrayListen Java o std::vectorC++. 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 llevarí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. De manera similar, las siguientes tres operaciones de inserción tomarían un tiempo constante, y luego la adición posterior requeriría otra lenta duplicación del tamaño de la matriz.
En general, si consideramos un número arbitrario de inserciones n + 1 en una matriz de tamaño n , notamos que las operaciones de inserción toman un tiempo constante, excepto la última que requiere tiempo para realizar la operación de duplicación de tamaño. Dado que hubo n + 1 operaciones en total, podemos tomar el promedio de esto y encontrar que insertar elementos en la matriz dinámica requiere: tiempo constante. [3]
Se muestra una implementación Python3 de una cola , una estructura de datos FIFO :
clase Cola : # Inicializa la cola con dos listas vacías def __init__ ( self ): self . input = [] # Almacena elementos que están en cola self . salida = [] # Almacena elementos que están fuera de cola def poner en cola ( self , elemento ): self . aporte . append ( elemento ) # Agregar el elemento a la lista de entrada def quitar cola ( self ): si no es self . salida : # 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 mientras self . input : # Mientras la lista de entrada no esté vacía self . producción . append ( self . input . pop ()) # Extraiga el último elemento de la lista de entrada y agréguelo a la lista de salida regresar a uno mismo . producción . pop () # Pop y devuelve el último elemento de la lista de salidaLa operación de puesta en cola simplemente empuja un elemento a la matriz 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 quitar la cola es más complicada. Si la matriz de salida ya tiene algunos elementos, entonces la eliminación de la cola se ejecuta en tiempo constante; de lo contrario, sacar de la cola toma tiempo para 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 de la entrada, podemos realizar n operaciones de eliminación de la 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 eliminación de la cola en solo tiempo, lo que implica que el tiempo amortizado de cada operación de eliminación de la cola es . [4]
Alternativamente, podemos cobrar el costo de copiar cualquier elemento de la matriz de entrada a la matriz de salida a la operación de puesta en cola anterior para ese elemento. Este esquema de cobro duplica el tiempo amortizado de la puesta en cola, pero reduce el tiempo amortizado de la cola a .
