tailieunhanh - Amortized Analysis
Not just consider one operation, but a sequence of operations on a given data cost over a sequence of operations. | Amortized Analysis (chap. 17) Not just consider one operation, but a sequence of operations on a given data structure. Average cost over a sequence of operations. Probabilistic analysis: Average case running time: average over all possible inputs for one algorithm (operation). If using probability, called expected running time. Amortized analysis: No involvement of probability Average performance on a sequence of operations, even some operation is expensive. Guarantee average performance of each operation among the sequence in worst case. Three Methods of Amortized Analysis Aggregate analysis: Total cost of n operations/n, Accounting method: Assign each type of operation an (different) amortized cost overcharge some operations, store the overcharge as credit on specific objects, then use the credit for compensation for some later operations. Potential method: Same as accounting method But store the credit as “potential energy” and as a whole. Example for amortized analysis Stack . | Amortized Analysis (chap. 17) Not just consider one operation, but a sequence of operations on a given data structure. Average cost over a sequence of operations. Probabilistic analysis: Average case running time: average over all possible inputs for one algorithm (operation). If using probability, called expected running time. Amortized analysis: No involvement of probability Average performance on a sequence of operations, even some operation is expensive. Guarantee average performance of each operation among the sequence in worst case. Three Methods of Amortized Analysis Aggregate analysis: Total cost of n operations/n, Accounting method: Assign each type of operation an (different) amortized cost overcharge some operations, store the overcharge as credit on specific objects, then use the credit for compensation for some later operations. Potential method: Same as accounting method But store the credit as “potential energy” and as a whole. Example for amortized analysis Stack operations: PUSH(S,x), O(1) POP(S), O(1) MULTIPOP(S,k), min(s,k) while not STACK-EMPTY(S) and k>0 do POP(S) k=k-1 Let us consider a sequence of n PUSH, POP, MULTIPOP. The worst case cost for MULTIPOP in the sequence is O(n), since the stack size is at most n. thus the cost of the sequence is O(n2). Correct, but not tight. Aggregate Analysis In fact, a sequence of n operations on an initially empty stack cost at most O(n). Why? Each object can be POP only once (including in MULTIPOP) for each time it is PUSHed. #POPs is at most #PUSHs, which is at most n. Thus the average cost of an operation is O(n)/n = O(1). Amortized cost in aggregate analysis is defined to be average cost. Another example: increasing a binary counter Binary counter of length k, A[0k-1] of bit array. INCREMENT(A) i 0 while i
đang nạp các trang xem trước
