Amortization: Difference between revisions
From charlesreid1
(Fix math rendering: replace \mbox with \text inside <math> tags for better renderer compatibility (via update-page on MediaWiki MCP Server)) |
|||
| (One intermediate revision by the same user not shown) | |||
| 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 13: | Line 15: | ||
* We also encountered them with hash tables and dynamic resizing of hash tables: [[Hash_Maps/Dynamic_Resizing#Amortization]] | * We also encountered them with hash tables and dynamic resizing of hash tables: [[Hash_Maps/Dynamic_Resizing#Amortization]] | ||
<math> | |||
\sum \text{actual cost} \leq \sum \text{amortized cost} | |||
</math> | |||
==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 28: | ||
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= | ||
Latest revision as of 23:19, 5 June 2026
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
$ \sum \text{actual cost} \leq \sum \text{amortized cost} $
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
|