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

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

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

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

3、beastackobject,ithastwobasicIntheworstcaseoftheseoperations,theoperations:worstcostisn,thesizeofthedadaPop()structure;Push()AsequenceofmoperationscostatmostAddinganotheroperationm*nMultiPop(k),whichpopskelementsatonce,itscostisatmostkpop()’scostTheamortizedcostof

4、theoperationsisAttention:whatitoccurswhenlessthanO(n)S.getSize()

5、ze()}operations0.IthasatleastmpushoperationhadtakenArrayA=[0,1,…,k-1]representsthekbitsbeforethepops.OnaninitialemptyStack,asequenceofnoperationsofpush,pop,multipoptakesatmostO(n)stepsofoperations.Amortizedcost=O(n)/n=O(1)清华大学宋斌恒7清华大学宋斌恒8CounterA[5]A[4]A[3]A[2]A[

6、1]A[0]TotalvaluecostAlgorithm000000001000001120000103Increment(A)300001141.iÅ040001007500010182.whilei

7、61601000031清华大学宋斌恒9清华大学宋斌恒10AnalysisthealgorithmTotalcostThemostcostingoperationisk,thelengthThetotalnumberofflips.ofthebits,theworstcostwillnotexceedO(nk)wherenistheoperationnumbers;Atightenanalysis⎣⎦lgni∞iHalftheoperationstake1operation∑i

8、erationstakes2operationsi=02i=02-iofoperationstakesioperations清华大学宋斌恒11清华大学宋斌恒122讨论小结长整数二进制加法的线性性证明：聚集分析方法关键点？高位相加快？低位相加快？或者一样？所有n个运算集中考虑不考虑不同运算的消费不同只考虑所有运算的总复