Hispanopedia Wiki
Articulo de referencia

Amortized analysis

In computer science , amortized analysis is a method for analyzing a given algorithm's complexity , or how much of a resource, especially time or memory, it takes to execute . T...

Hispanopedia WikiContenido en espanolLectura gratuita

In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute. The motivation for amortized analysis is that looking at the worst-case run time can be too pessimistic. Instead, amortized analysis averages the running times of operations in a sequence over that sequence.[1]:306 As a conclusion: "Amortized analysis is a useful tool that complements other techniques such as worst-case and average-case analysis."[2]:14[3]

For a given operation of an algorithm, certain situations (e.g., input parametrizations or data structure contents) may imply a significant cost in resources, whereas other situations may not be as costly. The amortized analysis considers both the costly and less costly operations together over the whole sequence of operations. This may include accounting for different types of input, length of the input, and other factors that affect its performance.[2]

History

Amortized analysis initially emerged from a method called aggregate analysis, which is now subsumed by amortized analysis. The technique was first formally introduced by Robert Tarjan in his 1985 paper Amortized Computational Complexity,[1] which addressed the need for a more useful form of analysis than the common probabilistic methods used. Amortization was initially used for very specific types of algorithms, particularly those involving binary trees and union operations. However, it is now ubiquitous and comes into play when analyzing many other algorithms as well.[2]

Method

Amortized analysis requires knowledge of which series of operations are possible. This is most commonly the case with data structures, which have a state that persists between operations. The basic idea is that a worst-case operation can alter the state in such a way that the worst case cannot occur again for a long time, thus "amortizing" its cost.

There are generally three methods for performing amortized analysis: the aggregate method, the accounting method, and the potential method. All of these give correct answers; the choice of which to use depends on which is most convenient for a particular situation.[4]

  • Aggregate analysis determines the upper bound T(n) on the total cost of a sequence of n operations, then calculates the amortized cost to be T(n) / n.[4]
  • The accounting method is a form of aggregate analysis which assigns to each operation an amortized cost which may differ from its actual cost. Early operations have an amortized cost higher than their actual cost, which accumulates a saved "credit" that pays for later operations having an amortized cost lower than their actual cost. Because the credit begins at zero, the actual cost of a sequence of operations equals the amortized cost minus the accumulated credit. Because the credit is required to be non-negative, the amortized cost is an upper bound on the actual cost. Usually, many short-running operations accumulate such credit in small increments, while rare long-running operations decrease it drastically.[4]
  • The potential method is a form of the accounting method where the saved credit is computed as a function (the "potential") of the state of the data structure. The amortized cost is the immediate cost plus the change in potential.[4]

Examples

Dynamic array

Amortized analysis of the push operation for a dynamic array

Consider a dynamic array that grows in size as more elements are added to it, such as ArrayList in Java or std::vector in C++. If we started out with a dynamic array of size 4, we could push 4 elements onto it, and each operation would take constant time. Yet pushing a fifth element onto that array would take longer as the array would have to create a new array of a scaled size, copy the old elements onto the new array, then add the new element. The next few push operations would similarly take constant time, then the subsequent addition would require another slow scaling of the array size.

In general, for an arbitrary number n{\displaystyle n} of pushes to an array of any initial size, the times for steps that scale the array add in a geometric series to O(n){\displaystyle O(n)}, while the constant times for each remaining push also add to O(n){\displaystyle O(n)}. Therefore the average time per push operation is O(n)/n=O(1){\displaystyle O(n)/n=O(1)}. This reasoning can be formalized and generalized to more complicated data structures using amortized analysis.[4]

Queue

Shown is a Python implementation of a queue, a FIFO data structure:

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(norte){\displaystyle 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 soloO(norte){\displaystyle O(n)}tiempo , lo que implica que el tiempo amortizado de cada operación de desencolado esO(1){\displaystyle 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){\displaystyle 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. 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 .
  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.
  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 .
  5. ↑ 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.