Amortization: Difference between revisions
From charlesreid1
(→Notes) |
|||
| Line 1: | Line 1: | ||
=Notes= | =Notes= | ||
An operation takes "T(n) amortized" if k operations take <math> \leq k \cdot T(n)</math> time | |||
k inserts take theta(k) time, so this is O(1) amortized insert | |||
Methods for amortized analysis: | Methods for amortized analysis: | ||
| Line 21: | Line 23: | ||
The downside is, mixing different operations makes things more complicated. | The downside is, mixing different operations makes things more complicated. | ||
== | ==More General Definition== | ||
The more general way of talking about an amortized bound is saying, each operation will have some particular cost that we assign it (amortized cost). We are then only required to preserve the sum of these costs. That is, | The more general way of talking about an amortized bound is saying, each operation will have some particular cost that we assign it (amortized cost). We are then only required to preserve the sum of these costs. That is, | ||
| Line 30: | Line 32: | ||
If we know that the amortized cost is at most constant, then we know that the actual cost is at most constant. This abstracts away costs of individual operations, only focusing on the overall cost. | If we know that the amortized cost is at most constant, then we know that the actual cost is at most constant. This abstracts away costs of individual operations, only focusing on the overall cost. | ||
==Links== | |||
See https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/lecture-notes/MIT6_046JS15_lec05.pdf | |||
=Flags= | =Flags= | ||
Revision as of 07:30, 2 July 2017
Notes
An operation takes "T(n) amortized" if k operations take $ \leq k \cdot T(n) $ time
k inserts take theta(k) time, so this is O(1) amortized insert
Methods for amortized analysis:
- Aggregate method - see below
- Accounting method - see Amortization/Accounting Method
- Charging method
- Potential method
Amortization of resizing:
- We already encountered amortized resizing with the Python dynamicaly-resized array data structure: Arrays/Python/DynamicArrayResizing
- We also encountered them with hash tables and dynamic resizing of hash tables: Hash_Maps/Dynamic_Resizing#Amortization
Aggregate Method
The simplest way of thinking about amortization is using the aggregate method: to compute the amortized cost per operation, we sum up the time for k operations, and divide by k.
Amortized cost per operation = ( total cost of k operations ) / ( k )
The downside is, mixing different operations makes things more complicated.
More General Definition
The more general way of talking about an amortized bound is saying, each operation will have some particular cost that we assign it (amortized cost). We are then only required to preserve the sum of these costs. That is,
$ \sum \mbox{actual cost} \leq \sum \mbox{amortized cost} $
If we know that the amortized cost is at most constant, then we know that the actual cost is at most constant. This abstracts away costs of individual operations, only focusing on the overall cost.
Links
Flags
 |
Algorithms Part of Computer Science Notes
Series on Algorithms
Algorithms/Sort · Algorithmic Analysis of Sort Functions · Divide and Conquer · Divide and Conquer/Master Theorem Three solid O(n log n) search algorithms: Merge Sort · Heap Sort · Quick Sort Algorithm Analysis/Merge Sort · Algorithm Analysis/Randomized Quick Sort
Algorithms/Search · Binary Search · Binary Search Modifications
Algorithms/Combinatorics · Algorithms/Combinatorics and Heuristics · Algorithms/Optimization · Divide and Conquer
Algorithms/Strings · Algorithm Analysis/Substring Pattern Matching
Algorithm complexity · Theta vs Big O Amortization · Amortization/Aggregate Method · Amortization/Accounting Method Algorithm Analysis/Matrix Multiplication
Estimation Estimation · Estimation/BitsAndBytes
Algorithm Practice and Writeups Project Euler · Five Letter Words · Letter Coverage
|