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:
“Protestantism has the method of Jesus with His secret too much left out of mind; Catholicism has His secret with His method too much left out of mind; neither has His unerring balance, His intuition, His sweet reasonableness. But both have hold of a great truth, and get from it a great power.”
—Matthew Arnold (1822–1888)
“The good husband finds method as efficient in the packing of fire-wood in a shed, or in the harvesting of fruits in the cellar, as in Peninsular campaigns or the files of the Department of State.”
—Ralph Waldo Emerson (1803–1882)
“You that do search for every purling spring
Which from the ribs of old Parnassus flows,
And every flower, not sweet perhaps, which grows
Near thereabouts into your poesy wring;
You that do dictionary’s method bring
Into your rhymes, running in rattling rows;”
—Sir Philip Sidney (1554–1586)