Method
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.
- 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.
- 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.
- The potential method is like the accounting method, but overcharges operations early to compensate for undercharges later.
Read more about this topic: Amortized Analysis
Famous quotes containing the word method:
“Direct action ... is the logical, consistent method of Anarchism.”
—Emma Goldman (1869–1940)
“One of the grotesqueries of present-day American life is the amount of reasoning that goes into displaying the wisdom secreted in bad movies while proving that modern art is meaningless.... They have put into practise the notion that a bad art work cleverly interpreted according to some obscure Method is more rewarding than a masterpiece wrapped in silence.”
—Harold Rosenberg (1906–1978)
“... the one lesson in the ultimate triumph of any great actress has been to enforce the fact that a method all technique or a method all throes, is either one or the other inadequate, and often likely to work out in close proximity to the ludicrous.”
—Mrs. Leslie Carter (1862–1937)