Algorithms & Data Structures (Winter 2021) Extras – Amortized Analysis
Announcements
Copyright By PowCoder代写 加微信 powcoder
• AmortizedAnalysis.
• Randomized algorithms. • ProbabilisticAnalysis.
• Review Final Exam.
Amortized Analysis – Introduction 1
When I say that you spend an average of 2 hours per week on assignments, I mean that this is the amount of work you do per week, averaged or “amortized” over the semester.
• There is nothing random going on here.
Amortized Analysis – Introduction 2
When you buy a house for 500K, you do not (usually) pay the whole amount up front and then live in it for free for n = 25 years. Rather, you pay say 100K and the bank pays 400K, and you make regular (equal) mortgage payments to the bank for n = 25 years. The amount is determined by an amortization table.
• There is nothing random going on here.
Amortized Analysis
• Analyze a sequence of operations on a data structure.
• We will talk about average performance of each operation in the worst case (i.e. not averaging over a distribution of inputs. No probability!)
• Goal: Show that although some individual operations may be expensive, on average the cost per operation is small.
• 3 methods:
1. aggregate analysis
2. accounting method
3. potential method (See textbook for more details)6
Amortized Analysis – Aggregate Analysis
• Goal: Show that although some individual operations may be expensive, on average the cost per operation is small.
• 3 methods:
1. aggregate analysis.
• A sequence of n operations takes worst-case time T(n) in total. In the worst case, the average cost, or amortized cost, per operation is therefore T(n)/n.
• Note that this amortized cost applies to each operation, even when there are several types of operations in the sequence.
• Although some operations might be expensive, many others might be cheap.
• 26 hours during the term (13 weeks) . You spend an average of 2 hours per week on assignments. T(n) = 26, T(n)/n = 2.
Aggregate Analysis – Example 1
Stack operations
• PUSH(S, x): O(1) each ⇒ O(n) for any sequence of n operations.
• POP(S): O(1) each ⇒ O(n) for any sequence of n operations.
• MULTIPOP(S,k):
while S≠Ø and k>0 do
POP(S) k⟵k−1
Running time of MULTIPOP?
Aggregate Analysis – Example 1
Running time of MULTIPOP:
• Let each PUSH/POP cost 1.
• # of iterations of while loop is min(s, k), where s = # of objects on stack.
Therefore, total cost = min(s, k).
Sequence of n PUSH, POP, MULTIPOP operations:
• Worst-case cost of MULTIPOP is O(n).
• Have n operations.
• Therefore, worst-case cost of sequence is O(n2).
• Each object can be popped only once per time that it is pushed.
• Have ≤ n PUSHes ⇒ ≤ n POPs, including those in MULTIPOP.
• Therefore, total cost = O(n).
• Average over the n operations ⇒ O(1) per operation on average.
Aggregate Analysis – Example 2
• k-bit binary counter A[0 . . k − 1] of bits, where A[0] is the least significant bit and A[k − 1] is the most significant bit.
• Counts upward from 0.
• Value of counter is: ∑A[i]⋅ 2i
• Initially,countervalueis0,soA[0..k−1]=0.
• To increment, add 1 (mod 2k ): Increment(A,k):
while i
Dynamic Tables – Expansion
Consider only insertion.
• When the table becomes full, double its size and reinsert all existing items.
• Guarantees that α ≥ 1⁄2.
• Each time we insert an item into the table, it is an elementary insertion.
TABLE-INSERT(T,x) if size[T ]=0
then allocate table[T] with 1 slot size[T]←1
if num[T]=size[T] then
allocate new-table with 2 · size[T] slots insert all items in table[T] into new-table free table[T]
table[T]←new-table
size[T]←2·size[T]
insert x into table[T] num[T]←num[T] + 1
(Initially, num[T]=size[T]= 0)
Dynamic Tables – Aggregate Analysis
• Cost of 1 per elementary insertion.
• Count only elementary insertions (other costs = constant).
ci = actual cost of ith operation
• If not full, ci =1.
• If full, have i−1 items in the table at the start of the ith operation.
Have to copy all i − 1 existing items, then insert ith item ⇒ ci = i. Naïve: n operations ⇒ ci = O(n) ⇒ O(n2) time for n operations
ci=$#i ifi−1ispowerof2
$% 1 Otherwise
n “#logn$% 2″#logn$%+1 −1
Totalcost= ∑c ≤n+ ∑2j =n+
i=1 j=0 Amortized cost per operation = 3.
Dynamic Tables – Accounting method
Charge $3 per insertion of x.
• $1 pays for x’s insertion.
• $1 pays for x to be moved in the future.
• $1 pays for some other item to be moved.
Dynamic Tables – Accounting method
Charge $3 per insertion of x.
• $1 pays for x’s insertion.
• $1 pays for x to be moved in the future.
• $1 pays for some other item to be moved.
Prove the credit never goes negative:
• size=m before and size=2m after expansion.
• Assume that the expansion used up all the credit, thus that there is
no credit available after the expansion.
• We will expand again after another m insertions.
• Each insertion will put $1 on one of the m items that were in the
table just after expansion and will put $1 on the item inserted.
• Have $2m of credit by next expansion, when there are 2m items to
move. Just enough to pay for the expansion…
• AmortizedAnalysis.
• Randomized algorithms. • ProbabilisticAnalysis.
• Review Final Exam.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com