算法分析与设计2005春.课件.第06讲b6 清华大学：算法分析与设计

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

1、Overview第六讲：分摊分析法AggregateanalysisTheaccountingmethodAmortizedAnalysisThepotentialmethodExample:宋斌恒Dynamictables清华大学宋斌恒1清华大学宋斌恒2Overview聚集分析法由分摊分析法解决的问题Asequenceofnoperationstakesworst-SequenceofoperationonadadastructurecasetimeT(n)intotalAveragecostperoperationTheaveragecostT(n)/niscall

2、edthe【比如网站的整体效率问题与此问题的关系】amortizedcost,三类主要分析手段theamortizedcostappliestoeachAggregate,worstcase+averageoperation,eventheyaredifferent.Accounting,AmortizedcostPotential,isawholeindexforthedatastructure清华大学宋斌恒3清华大学宋斌恒4Stackoperation粗略分析LetSbeastackobject,ithastwobasicIntheworstcaseoftheseo

3、perations,theoperations:worstcostisn,thesizeofthedadaPop()structure;Push()AsequenceofmoperationscostatmostAddinganotheroperationm*nMultiPop(k),whichpopskelementsatonce,itscostisatmostkpop()’scostTheamortizedcostoftheoperationsisAttention:whatitoccurswhenlessthanO(n)S.getSize()

4、tbutnottight!清华大学宋斌恒5清华大学宋斌恒61聚集分析法示例：计数器Considertheentiresequenceofoperations:Considertheproblemofincrementingak-AMultiPop(k)takesatmostm=min{k,bitbinarycounterthatcountsupwardfromS.getSize()}operations0.IthasatleastmpushoperationhadtakenArrayA=[0,1,…,k-1]representsthekbitsbeforethepops

5、.OnaninitialemptyStack,asequenceofnoperationsofpush,pop,multipoptakesatmostO(n)stepsofoperations.Amortizedcost=O(n)/n=O(1)清华大学宋斌恒7清华大学宋斌恒8CounterA[5]A[4]A[3]A[2]A[1]A[0]TotalvaluecostAlgorithm000000001000001120000103Increment(A)300001141.iÅ040001007500010182.whilei

6、0110103.{7000111118001000151.A[i]Å0;9001001162.i++;10001010184.}110010111912001100225.ifi

7、O(nk)wherenistheoperationnumbers;Atightenanalysis⎣⎦lgni∞iHalftheoperationstake1operation∑i