Amortized analysis

Amortized analysis

In computer science, especially analysis of algorithms, amortized analysis refers to finding the average running time per operation over a worst-case "sequence" of operations. Amortized analysis differs from average-case performance in that probability is not involved; amortized analysis guarantees the time per operation over worst-case performance.

The method requires knowledge of which series of operations are possible. This is most commonly the case with data structures, which have 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.

As a simple example, in a specific implementation of the dynamic array, we double the size of the array each time it fills up. Because of this, array reallocation may be required, and in the worst case an insertion may require O("n"). However, a "sequence" of "n" insertions can always be done in O("n") time, so the "amortized" time per operation is O("n") / "n" = O(1).

Notice that average-case analysis and probabilistic analysis are not the same thing as amortized analysis. In average-case analysis, we are averaging over all possible inputs; in probabilistic analysis, we are averaging over all possible random choices; in amortized analysis, we are averaging over a sequence of operations. Amortized analysis assumes worst-case input and typically does not allow random choices.

There are several techniques used in amortized analysis:

*Aggregate analysis determines the upper bound "T"("n") on the total cost of a sequence of "n" operations, then calculates the average cost to be "T"("n") / "n".

*Accounting method determines the individual cost of each operation, combining its immediate execution time and its influence on the running time of future operations. Usually, many short-running operations accumulate a "debt" of unfavorable state in small increments, while rare long-running operations decrease it drastically.

*Potential method is like the accounting method, but overcharges operations early to compensate for undercharges later.

Common use

* In common usage, an "amortized algorithm" is one that an amortized analysis has shown to perform well.
* Online algorithms commonly use amortized analysis.

References

* cite book | author= Allan Borodin and Ran El-Yaniv | title= [http://www.cs.technion.ac.il/~rani/book.html "Online Computation and Competitive Analysis"]
publisher= Cambridge University Press
date= 1998 | pages= 20,141

* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. "Introduction to Algorithms", Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 17: Amortized Analysis, pp.405–430.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Analysis of algorithms — To analyze an algorithm is to determine the amount of resources (such as time and storage) necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length. Usually the efficiency or running time of an algorithm is… …   Wikipedia

  • Competitive analysis (online algorithm) — Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is …   Wikipedia

  • Probabilistic analysis of algorithms — In analysis of algorithms, probabilistic analysis of algorithms is an approach to estimate the computational complexity of an algorithm or a computational problem. It starts from an assumption about a probabilistic distribution of the set of all… …   Wikipedia

  • Accounting method — In computational complexity theory, the accounting method is a method of amortized analysis based on accounting. The accounting method often gives a more intuitive account of the amortized cost of an operation than either aggregate analysis or… …   Wikipedia

  • Dynamic array — Several values are inserted at the end of a dynamic array using geometric expansion. Grey cells indicate space reserved for expansion. Most insertions are fast (constant time), while some are slow due to the need for reallocation (Θ(n) time,… …   Wikipedia

  • Potential method — In algorithms, the potential method is a method used to analyze the amortized time and space complexity of an algorithm. It can be thought of as a generalization of the accounting method and the debit method. It is useful in cases where it is… …   Wikipedia

  • Análisis de amortización — Saltar a navegación, búsqueda En ciencias de la computación, especialmente el análisis de algoritmos, el análisis de amortización considera el promedio de tiempo de ejecución por más de una operación peor de los casos, la secuencia de las… …   Wikipedia Español

  • Best, worst and average case — In computer science, best, worst and average cases of a given algorithm express what the resource usage is at least , at most and on average , respectively. Usually the resource being considered is running time, but it could also be memory or… …   Wikipedia

  • List of mathematics articles (A) — NOTOC A A Beautiful Mind A Beautiful Mind (book) A Beautiful Mind (film) A Brief History of Time (film) A Course of Pure Mathematics A curious identity involving binomial coefficients A derivation of the discrete Fourier transform A equivalence A …   Wikipedia

  • List of computer scientists — Expand list|date=August 2008This is a list of well known computer scientists, people who do work in computer science, in particular researchers and authors.Some persons notable as programmers are included here because they work in research as… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”