资源描述
通信网络理论基础,Part02:算法简介分治,2/39,Algorithm的由来,2017年春季通信网络理论基础,3/39,算法是什么？,2017年春季通信网络理论基础,设计范型,2017年春季通信网络理论基础,436,分治、贪心、动态规划、蛮力、随机算法、回溯、分支定界，等等。,没有哪种范型能适用于所有问题。,也可以看作是分析问题的思路。,从问题到求解思路的思考方向。,5/39,DivideandConquer（DC）,2017年春季通信网络理论基础,一种直观的、最基础的范型。,例子,6/39,2017年春季通信网络理论基础,7/39,折半查找请查错，并修改Hint:以A=2,5,9x=5为例来思考。,伪码及实例,2017年春季通信网络理论基础,更好的例子：归并排序,2017年春季通信网络理论基础,836,经典：以至于几乎每本算法教材都用它来引出分治。,为啥说“更好”？,有效：排序是一个重要的算法问题，归并排序是最好的排序算法之一。,本课程将用它来引入复杂度分析的概念和基本原则。,对它的分析方法可以方便地扩展到“主定理”的证明。,递归：一个程序员永远的梦魇。,MergeSort,2017年春季通信网络理论基础,936,递归返回后如何合并？,MergeStep（合并步骤）,2017年春季通信网络理论基础,1036,运行时间(RT)是多少？,运行环境,CPU/OS/编译器,指令的类别,只去数操作的次数。,问题实例？,问题实例规模的函数。,Mergestep的RT(T(m)？,初始化：2,每次循环：4,RT：MergeSort,2017年春季通信网络理论基础,1136,Level0:最外层调用；问题的规模是n。,Level1:第一次调用递归,叶子：每个子问题都只含有1个元素的数组。,叶子在第几层？,递归树,第j层有几个子问题？,第j层子问题的规模？,/,子问题的RT？,/,第j层所有子问题的总工作量？,(/)=,Total？,(+).QED,复杂度分析的原则,2017年春季通信网络理论基础,1236,原则1:只关注“最坏情况”。,原则2:忽略常数和低阶项,任何规模为n的实例的操作时间的上界。,WHY?,WHY?,Moore定律=在大规模实例下讨论算法的运行时间才有意义。,理解复杂度分析,2017年春季通信网络理论基础,1336,不代表A的耗时总是少于B。,根据复杂度分析的结果说算法A比B好，是什么意思?,只能说随着实例规模的增加，A的耗时增长更慢。,只能在“分类”的意义上评论好坏。,粗糙的分类评判，真的有意义吗?,是的，还是有意义,2017年春季通信网络理论基础,1436,能够用多项式算法求解的问题=“易解”,只能用指数或阶乘算法求解的问题=“不易解”,粗糙的定量评判也比经验性的定性评判要好。,能够揭示问题本质上的难易程度。,只凭少量实例得到的判断很难得到有价值的结论。,函数增长的渐近记号,2017年春季通信网络理论基础,1536,令=,我们说=()是什么意思?,意味着n大到一定程度后，T(n)一定小于f(n)的常数倍。,BigO的证明（例1）,2017年春季通信网络理论基础,1636,例1:=+，证明:=,证明要点：选择合适的常数和，保证不等式成立。,待证：,+=QED,BigO的证明（例2）,2017年春季通信网络理论基础,1736,例2：证明:,证明要点：反证法。,BigOmega和BigTheta,2017年春季通信网络理论基础,1836,例子与练习,2017年春季通信网络理论基础,1936,例3：+=()()(),课后思考:=+，证明:=,课堂练习:证明例3,MergeSort：Revisit,2017年春季通信网络理论基础,2036,再来看这个结论，请问MergeSort的复杂度/RT是多少？,(),为什么不是()？,以任何常数为底，对数函数都只差常数倍。,这在众多的排序算法中，算是什么水平？,任何“基于比较”的排序算法中，最好的那一类即渐进最优算法。,基于比较的排序,2017年春季通信网络理论基础,2136,任何基于两两比较的排序算法都可以表达为一棵决策树。,给定问题实例2,6,8决策过程是什么？,给定7,3,5呢？,显然，这是一棵完全二叉树。,这是什么算法？,插入排序,决策树模型的性质,2017年春季通信网络理论基础,2236,一次排序所需要的比较次数等于路径长度。,上界为树高h。,任何正确的排序算法都应该可以检查到所有可能的排列。,所有排列都应在叶子节点出现。,叶节点数目l：!,完全二叉树中，l和h什么关系？,故有：!,!=(),QED,思考题作业,2017年春季通信网络理论基础,2336,我们没有给出MergeSort的详细伪码。主要是没有考虑边界条件（例如n不是2的幂的情况）。请你自己根据你的经验和理解来写出一般情况下的算法伪码。然后将你的伪码与正确伪代码对比。注意体会：与正确伪代码相比，你少考虑了什么？下周堂上讨论各自的体会。,这是一种很好的编程技能的训练和经验的积累，务必先做后对比。希望以后自己也常做类似练习。,另一个分治的例子,2017年春季通信网络理论基础,2436,都还记得小学老师教的吧？算法复杂度？,(),CANWEDOBETTER？,每个学算法的人都要让自己成为偏执狂。,如何分治？,=+=+,a,b,c,d都是n/2位的整数。,例如：=,=,=,两个递归算法,2017年春季通信网络理论基础,2536,=+=+,分解方式也有了，合并公式也有了，设计个递归吧？,=+,合并公式,GaussTrick:只用3个递归输出同样可以计算合并公式。,哪个更好？,2017年春季通信网络理论基础,2636,两个算法在递归调用之外做了哪些工作？,=+,ALG#1：计算合并公式。=(),ALG#2：计算合并公式；额外的加法。=(),画个递归树来求解？,也行。但有个更好的办法。,递归式,2017年春季通信网络理论基础,2736,主方法：用来求解递归式的一种方法。【“BlackBox”】,递归式是什么？,基于分治的递归算法的RT，通常可以表达出递归式。,ALG#1：=+(),ALG#2：=+(),=+()是什么算法？,MergeSort,主方法(MasterMethod),2017年春季通信网络理论基础,2836,对数的底到底要不要出现？,有时必须要；有时不必。,求解的例子(1/2),2017年春季通信网络理论基础,2936,例1：MergeSort,=+(),复杂度？,=,=,=,例2：=+(),复杂度？,=,=,=,这个算法你觉得奇怪吗？,求解的例子(2/2),2017年春季通信网络理论基础,3036,例3：ALG#1,=+(),复杂度？,=,=,=,例4：ALG#2,=+,复杂度？,=,=,=,高斯还是真的牛人啊。,证明主定理,2017年春季通信网络理论基础,3136,令=，并且+。【BigO的定义】,假定n是b的幂。【一般情况的证明思路类似】,基本思路：扩展MergeSort的分析方法递归树。,Level0:最外层调用；问题的规模是n。,Level1:a个子问题，n/b,叶子：子问题规模为1。Level,第j层的子问题数目？,第j层的子问题规模？,第j层总的RT？,=,总RT？,=,对参数的理解,2017年春季通信网络理论基础,3236,+,()=,a是什么？,子问题数目的增长速率。,是什么？,每个子问题RT的缩减速率。,=意味着什么？,意味着什么？,RT逐层增加。,叶节点的RT占主导。,关于求和的一个基本事实,2017年春季通信网络理论基础,3336,令,则有：=+,关键是：若，则上式为。若时，,而,=(),有点儿没对？=?,没错。两边都取对数，以b为底。即可得证。,主定理证毕,你来试试？,2017年春季通信网络理论基础,3636,请用主定理来分析下面两个算法的复杂度/RT.,课堂练习1:分治求数组的最大值。【有点侮辱智商】,课堂练习2:MergeSort-3。即每次分解为3个子问题。【不见得哦】,小结,2017年春季通信网络理论基础,3736,分治的概念,归并排序,复杂度分析,主方法,
展开阅读全文