算法分析与设计2004春.课件.第06讲

《算法分析与设计2004春.课件.第06讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六讲：分摊分析法AmortizedAnalysis宋斌恒清华大学宋斌恒1Overview•Aggregateanalysis•Theaccountingmethod•Thepotentialmethod•Example:–Dynamictables清华大学宋斌恒21Overview•ProblemssolvedbyAmortizedAnalysis–Sequenceofoperationonadadastructure–Averagecostperoperation–【比如网站的整体效率问题与此问题的关

2、系】•Threemainanalysismethods–Aggregate,worstcase+average–Accounting,Amortizedcost–Potential,isawholeindexforthedatastructure清华大学宋斌恒3Aggregateanalysis•Asequenceofnoperationstakesworst-casetimeT(n)intotal•TheaveragecostT(n)/niscalledtheamortizedcost,•theamor

3、tizedcostappliestoeachoperation,eventheyaredifferent.清华大学宋斌恒42Stackoperation•LetSbeastackobject,ithastwobasicoperations:–Pop()–Push()•Addinganotheroperation–MultiPop(k),whichpopskelementsatonce,itscostisatmostkpop()’scost•Attention:whatitoccurswhenS.getSi

4、ze()

5、uenceofoperations:•AMultiPop(k)takesatmostm=min{k,S.getSize()}operations•Ithasatleastmpushoperationhadtakenbeforethepops.•OnaninitialemptyStack,asequenceofnoperationsofpush,pop,multipoptakesatmostO(n)stepsofoperations.•Amortizedcost=O(n)/n=O(1)清华大学宋斌恒7Exa

6、mple:Incrementingabinarycounter•Considertheproblemofincrementingak-bitbinarycounterthatcountsupwardfrom0.•ArrayA=[0,1,…,k-1]representsthekbits清华大学宋斌恒84Algorithm•Increment(A)1.iÅ02.whilei

7、学宋斌恒9CounterA[5]A[4]A[3]A[2]A[1]A[0]Totalvaluecost00000000100000112000010330000114400010075000101860001101070001111180010001590010011610001010181100101119120011002213001101231400111025150011112616010清华大学宋斌恒00031105Analysisthealgorithm•Themostcostingoperat

8、ionisk,thelengthofthebits,theworstcostwillnotexceedO(nk)wherenistheoperationnumbers;•Atightenanalysis–Halftheoperationstake1operation–Quarteroftheoperationstakes2operations–2-iofoperationstakesioperations清华大学宋斌恒11To