Amortized analysis

From Wikipedia, the free encyclopedia
  (Redirected from Amortized time)
Jump to: navigation, search
"Amortized" redirects here. For other uses, see Amortization.

In computer science, amortized analysis is a method of analyzing algorithms that considers the entire sequence of operations of the program. It allows for the establishment of a worst-case bound for the performance of an algorithm irrespective of the inputs by looking at all of the operations. This analysis is most commonly discussed using big O notation.

At the heart of the method is the idea that while certain operations may be extremely costly in resources, they cannot occur at a high enough frequency to weigh down the entire program because the number of less costly operations will far outnumber the costly ones in the long run, "paying back" the program over a number of iterations.[1] It is particularly useful because it defines the worst-case limit of a program's performance rather than making assumptions about the state of the program.

History[edit]

Amortized analysis initially emerged from a method called aggregate analysis, which is now subsumed by amortized analysis. However, the technique was first formally introduced by Robert Tarjan in his 1985 paper Amortized Computational Complexity, which addressed the need for 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.[1]

Method[edit]

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.

There are generally three methods for performing amortized analysis: the aggregate method, the accounting method, and the potential method. All of these give the same answers, and their usage difference is primarily circumstantial and due to individual preference.[2]

  • 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.[2]
  • The 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.[2]
  • The potential method is like the accounting method, but overcharges operations early to compensate for undercharges later.[2]

Common use[edit]

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

References[edit]

  1. ^ a b Rebecca Fiebrink (2007), Amortized Analysis Explained, retrieved 2011-05-03 
  2. ^ a b c d Vijaya Ramachandran (2006), CS357 Lecture 16: Amortized Analysis, retrieved 2011-05-03 [dead link]