Comment on page
Analysis
- formal definition:if there exists positive constantsandsuch thatfor all.
-
notation | (literal) meaning | example 1 | example 2 | example 3 |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
- the hiring problem: in average O(log(n)) instead of O(n)
- quicksort: the cost is O(n log(n)) on average
- hash table: expected O(1)
- Rabin-Karp: sub-string matching
Though the algorithm is deterministic, the cost of each step may be different
- Binary Counter and Piggy Bank
- pay only when a bit changes from 0 to 1
- Hash Table
- load factor better to be 1/2
- need to resize when full
- worst case cost: O(n)
- amortized to O(1)
- Union-find with path-compression: O(log* n) per union or per find
- Weight balanced tree with rebuilding
- O(log n) cost per insertion
- O(1) cost for rebalance per insertion
- O(log n) cost for insertion itself
- Direct: count the total cost from an empty state all the way to the n-th operation O(f(n))
- then the total cost of each operation is
- Piggy bank: pay O(k) “dollars” per operation
- show that even though some of the operations are more expensive, the total cost of all n elements are no more than O(nk)
- Potential function: design a potential functionfor a certain state, and analyze the change of, from which we can derive the amortized cost
Last modified 2yr ago