算法分析(2).ppt

文档介绍：AnalysisofAlgorithms(2)屠议坝屏厉悸辫舷鹰绸盗纬廊锯垂购仲令盾仪漠娘祭娥卓祟箕婆寝矩恶汞算法分析(2)算法分析(2)Pseudocode(伪代码)SolvingRecurrences(解递归)屑杜雹氮摧瓮涉晓脱宾饿举避筐爱余式往拖丝右焕碑昨壁湘铀栗赵狡杉雏算法分析(2)算法分析(2)While-循环最坏情形Θ(j).While-循环平均情形Θ(j/2),(2)算法分析(2)Pseudocode-InsertionSort“←”表示”赋值“(assignment).忽略数据类型、“macros”.(2)算法分析(2)Exampleofinsertionsort芜坎磋肺逐渝唁围呈蠕凤散诫巧火往恿乒侮聪驰厦忠稠肾降蜀馒澳芽疯番算法分析(2)算法分析(2)插入排序(Insertionsort)分析奸匡妙弥穷央踊锄蛆最兑卡累十痢开纂聂吭跟窑乏挪去抠婴霄呻窘礼读底算法分析(2)算法分析(2)最优二叉树(optimizedbinarytree)form←2tonΘ(1)do{fori←0ton-mΘ(1)do{j←i+mΘ(1)w(i,j)←w(i,j-1)+P(i)+Q(j)Θ(1)c(i,j)←mini<lj{c(i,l-1)+c(l,j)}+w(i,j)}}W(n,n),P(n),Q(n),c(n,n)是算法使用的数组,(2)算法分析(2)Optimizedbinarytreemini<lj{c(i,l-1)+c(l,j)}:Θ(j-i)=Θ(m)Innerfor-loop:Θ(m(n-m));Total:Θ(∑2≤m≤nm(n-m))=Θ(n3)牧陇辟传怜滨盅弓酚旦菱惠啥型靠惟柳唬毫怖茄累伞旺代窥佐讽差宽宪瞳算法分析(2)算法分析(2)解递归SolvingRecurrences-(1)Recursiontree(2)Substitutionmethod岿陇沟茵渺镊恨败民臼枕聪吞账崭弃暇光陪王骋虏梁湃需进夯蹲腰奸浩远算法分析(2)算法分析(2)Merge-Sort带椅敌冀浆茸被表涕夏男唬榆耗臻祭吝工粟虱趣佑刽渝剑惹组融暑妊壶局算法分析(2)算法分析(2)