算法分析英文分期清嘗amortized

1、Algorithms Design and Analysis:Amortized AnalysisProf. Dr. Jinxing XieDept. of Mathematical SciencesTsinghua University, Beijing 100084, China Voice:(86-10)62787812 Fax:(86-10)62785847What is an amortized analysis? The time required to perform a sequence of data-structure operations is averaged over

2、 all the operations performed. Used to show the average cost of an operationA sequence of operationstimeaverageAmortized Analysis Differs from average-case analysis: Probability is not involved; Guarantees the average performance of each operation in the worst case Three techniques: Aggregate analys

3、is Accounting method Potential methodExample:Increasing a k-bit binary counterIncreasing a k-bit binary counterImplementing a k-bit binary counter that counts upward from 0: A0.k-1 for bits, where lengthA=k. x: lowest-order bit in A0 and highest-order bit in Ak-1 Initially, assume x=0 Aggregate anal

4、ysis A sequence of n operations takes worst-case time T(n) in total Amortized cost per operation, in the worst case, is T(n)/nThe algorithmFirst glance:(Worst case) Each time: Total: O(nk)Can we do better?Aggregate analysis:Average cost per operationA0: flips each timeA1: flips every other timeA2: f

5、lips every fourth timeAk-1: flips every 2k-1-th timeFor a sequence of n INCREMENTs:Average cost (amortized cost) per operation:The accounting methodAssign differing charges (amortized cost) to different operations, with some operations charged more or less than they actually cost. When an operations

6、 amortized cost exceeds its actual cost, the difference is assigned to specific objects in the data structure as credit.Credit can be used later on to help pay for operations whose amortized cost is less than their actual cost.Attention: Total credit stored in the data structure should never es nega

7、tive!Assume flipping a bit costs a dollar:Charge an amortized cost of 2 dollars to set a bit to 1Credit on “1”: 1 dollarExample: INCREMENTWhen a bit is set, we use 1 dollar to pay for the actual setting of the bit, and place the other dollar on the bit as credit to be used later when we flip the bit

8、 back to 0.Every “1” has a dollar of credit on it, thus we need not charge anything to rest a bit to 0Credit never es negative!In each operation, at least one bit is set: cost 2 dollarsTotal cost for n operations: O(n)Potential methodRepresents the prepaid work as “potential energy” or just “potenti

9、al”, that can be released to pay for future operations. The potential is associated with the data structure as a whole rather than with specific objects within the data structureInitial data structure: D0For each i=1,2,n, let ci be the actual cost of the ith operation and Di be the data structure af

10、ter applying the ith operation to data structure Di-1Potential function:Amortized cost: Example: INCREMENTDefine the potential function: bi = the number of 1s in the counter after the ith operationSuppose the ith operation resets ti bits (to 0)The actual cost of the operation is at most ci 0, then b

11、i = bi-1 - ti +1bi = 0.5) TableTTABLE-INSERTElementary insertion: cost=1Initial Analysis for n consecutive insertions (starting with an empty table)ith insertion costs ci:- If there is room in current table (or its the first operation), ci=1 If the table is full, need (i-1) copies (insertions), ci=i

12、 In worst-case, an operation costs O(n)Totally O(n2)Full tablenew tablecopyxAggregate AnalysisTotallyAverage cost of an operation: O(1)Charge each insertion 3dollars:- One for the current insertion;- The second for the immediate moving of itself when the table is expanded The third is for the item a

13、lready moved onceWhen the table is full, each item has a dollar to pay for its reinsertion during the expansionAccounting AnalysisCharge each insertion 3dollars:- One for the current insertion;- The second for the immediate moving of itself when the table is expanded The third is for the item alread

14、y moved onceWhen the table is full, each item has a dollar to pay for its reinsertion during the expansionPotential methodNonnegative: numT = sizeT /2Immediately after an expansion: Immediately before an expansion:Potential methodLet numi denote numT after ith insertion Let sizei denote sizeT after

15、ith insertionIf the ith insertion does not trigger an expansion:If the ith insertion does trigger an expansion:Both Insertion & DeletionInsertion can cause expansion of the tableDeletion can cause contraction of the table Contract whenever load factor 0.5? numT=4 1 2 3 4 5 6 7 8 sizeT=8 load factor=

16、0.5TableTdeleteTableTdeleteNew tableContract whenever load factor 0.5First n/2 insertions, where n is an exact power of 2The following n/2 operations: I, D, D, I ,I, D, D, I, I, The cost of each expansion or contraction is Totally Amortized cost of an operationTableTTableTdeleteTableTContract whenev

17、er deleting at load factor = The contraction assure that the load factor is 1? - No! Its not a good idea! - Halve the table size maybe better (load factor 1/2)Whats the complexity of a sequence of n insertions and deletions? - Really challenging !TableTTableTTABLE-DELETEElementary deletion: cost=1Po

18、tential method When load factor=1, i.e. numT=sizeT, thus potential=numT can pay for an expansion if an item is inserted When load factor=1/4, i.e. sizeT=4*numT, thus potential=numT can pay for a contraction if an item is deleted Contract whenever deleting at load factor = When the operation is insertion:After ith operationIf Identical to previous discussionIfIfContract whenever deleting at load factor = When the operation is deletion:After ith operationIfIfContract wheneve