《电子科技大学通信网理论基础孙罡02-算法与分治-2017》由会员分享，可在线阅读，更多相关《电子科技大学通信网理论基础孙罡02-算法与分治-2017（37页珍藏版）》请在金锄头文库上搜索。
1、通信网络理论基础Part 02: 算法简介分治2 / 39Algorithm的由来Why ?因为：一个使得定量分析大众化了，另一个使得知识大众化了。1448=MCDXLVIIIAlgorithmTo honor the wise Arabian:Al KhwarizmiAD 600十进制计数法及其符号在印度 (注意，不是阿拉伯 )被发明。DecimalNine CenturyAlKhwarizmi(Baghdad)写了一本介绍十进制以及相应的四则运算 (甚至还包括求平方根和求 PIE)方法的阿拉伯文教材。并在很多个世纪之后被介绍到了西方。Algorithm1448一个 Mainz(德国城市 )
2、的金匠 ， JohannGutenberg，发明了金属活字印刷。TypographyTheDarkAgesended,thehumanintellectwasliberated,scienceandtechnologytriumphed,theIndustrialRevolutionhappened.Two ideas changed the world因为那些计算方法具有 “算法 ”的一切 特征Precise/Unambiguous/Mechanical/Efficient/CorrectWhy ?2017年春季通信网络理论基础3 / 39算法是什么？求解问题的一个过程 (Procedure
3、)。算法过程由一系列步骤构成，其中每个步骤都是简单的，无歧义的，容易实现的。给定任意实例，都能给出所要求的结果。求解对一系列 (甚至无穷多个 )实例的统一 /无歧义的描述。由输入 (给定条件 )和输出 (待求结果 )组成。对一系列 甚至无穷多个 实例的统一 无歧义的描述。由输入 给定条件 和输出 待求结果 组成。问题问题问题 给定一组整数，求其中最大值。过程过程 比较前 2个数的大小，较大者与第 3个比； 例子2017年春季通信网络理论基础设计 范型2017年春季通信网络理论基础4 36Design Paradigm。可以看作设计算法的通用思路。范型分治、贪心、动态规划 、蛮力、随机算法、回溯
4、、分支定界，等等。没有哪种范型能适用于所有问题 。也可以看作是分析问题的思路 。从问题到求解思路的思考方向。5 / 39Divide and Conquer（ DC） 将原问题分解为规模较小的子问题，将子问题的解组合成原问题的解。 注意，不是拆分成性质不同的多个逻辑步骤。Divide 如果子问题仍然困难，就继续对子问题进行分解。 直到最终分解得到的子问题变得容易 “征服”(trivial)。Conquer由于所有拆分出来的子问题都是相同性质的，因此可以方便地用递归(Recursion)方式来实现。Recursion2017年春季通信网络理论基础一种直观的、最基础的范型 。例子6 / 39例 1
5、求最大值在一组整数中求最大值 。分成两组，分别求最大值，然后比较这两个值，较大者作为原问题的解 。递归。例 2查找在一组升序整数中，查找某个特定的整数 。折半查找。例 3遍历在图中遍历所有的节点 。深度优先 遍历 (DFS)2017年春季通信网络理论基础7 / 39折半查找请查错，并修改Hint:以 A=2,5,9x=5为例来思考。伪码及实例Functionsearch(A,x,k,r)/findxinAk.rIFk=rTHENRETURN(k)ELSEm=(k+r)/2IFxAmTHENRETURN(search(A,x,k,m)ELSERETURN(search(A,x,m,r)基于 DC
6、的求最大值Functionmaximum(S,x,y)/returnmaximuminSx.yIFyx1THENRETURN(max(Sx,Sy)ELSEm1=maximum(x,(x+y)/2)m2=maximum(x+y)/2+1,y)RETURN(max(m1,m2)伪码伪码2017年春季通信网络理论基础更好的例子： 归 并排序2017年春季通信网络理论基础8 36经典：以至于几乎每本算法教材都用它来引出分治。为啥说 “更好 ”？有效：排序是一个重要的算法问题，归并排序是最好的排序算法之一。本课程将用它来引入复杂度分析的概念和基本原则。对它的分析方法可以方便地扩展到 “主定理 ”的证明。
7、递归：一个程序员永远的梦魇。Merge Sort2017年春季通信网络理论基础9 36问题定义 输入： n个数构成的数组；无序；输出：按升序（或降序）排序。MergeSort假定 n为 2的幂。分解：对原数组等分为两个子数组。求解：递归地对两个子数组分别排序。合并：将两个已排序的子数组进行合并。5 4 1 8 67 325 4 1 8 67 325 4 1 8 7 2 6 3递归返回后如何合并？Merge Step（合并步 骤）2017年春季通信网络理论基础10 36merge-step(A,B,C)/C:输出数组，长度为 m/A:第一个已排序数组，长度为 m/2/B:第二个已排序数组，长度为
8、 m/2i=1;j=1;FORk=1tomIFAi在大规模实例下讨论算法的运行时间才有意义。理解复 杂 度分析2017年春季通信网络理论基础13 36不代表 A的耗时总是少于 B。根据复杂度分析的结果说算法 A比 B好，是什么意思 ?上界 =最坏情况不见得总是出现；单纯形 vs椭球只能说随着实例规模的增加， A的耗时增长更慢。只能在 “分类 ”的意义上评论好坏。“同类 ”算法已无法区分；快排 vs归并粗糙的分类评判，真的有意义吗 ?忽略常数和低阶 =只能预测趋势；归并 vs选择总得看一遍输入吧线性就是最好了 ?除非有额外信息是的， 还 是有意 义2017年春季通信网络理论基础14 36能够用多
9、项式算法求解的问题 =“易解 ”只能用指数或阶乘算法求解的问题 =“不易解 ”粗糙的定量评判也比经验性的定性评判要好。能够揭示问题本质上的难易程度。只凭少量实例得到的判断很难得到有价值的结论。函数增 长 的 渐 近 记 号2017年春季通信网络理论基础15 36意味着 n大到一定程度后， T(n)一定小于 f(n)的常数倍。BigO 常数的含义：不依赖于 n请仔细体会 “增长趋势 ”的含义请注意： 这不仅是定义，也是证明的主要（差不多是唯一）依据。BigO的 证 明（例 1）2017年春季通信网络理论基础16 36BigO的 证 明（例 2）2017年春季通信网络理论基础17 36证明要点：反
10、证法。BigOmega和 BigTheta2017年春季通信网络理论基础18 36BigOmega BigTheta 例子与 练习2017年春季通信网络理论基础19 36课堂练习 : 证明例 3MergeSort： Revisit2017年春季通信网络理论基础20 36CLAIM 再来看这个结论，请问 MergeSort的复杂度 /RT是多少？以任何常数为底，对数函数都只差常数倍。这在众多的排序算法中，算是什么水平？任何 “基于比较 ”的排序算法中，最好的那一类即渐进最优算法。基于比 较 的排序2017年春季通信网络理论基础21 36CLAIM a:bb:cb,a,ca:ca:cb:cb,c,
11、a c,b,ac,a,ba,c,ba,b,c任何基于两两比较的排序算法都可以表达为一棵决策树。树上节点：比较操作叶子节点：比较结果针对给定实例，算法运行过程对应从根到叶的一条路径。给定问题实例 2,6,8决策过程是什么？给定 7,3,5呢？显然，这是一棵完全二叉树。 这是什么算法？ 插入排序决策 树 模型的性 质2017年春季通信网络理论基础22 36a:bb:cb,a,ca:ca:cb:cb,c,a c,b,ac,a,ba,c,ba,b,c一次排序所需要的 比较次数 等于路径长度。上界为树高 h。任何正确的排序算法都应该可以检查到所有可能的排列。所有排列都应在叶子节点出现。完全二叉树中， l
12、和 h什么关系？QED思考 题 作 业2017年春季通信网络理论基础23 36我们没有给出 MergeSort的详细伪码。主要是没有考虑边界条件（例如 n不是 2的幂的情况）。请你自己根据你的经验和理解来写出一般情况下的算法伪码。然后将你的伪码与正确伪代码对比。注意体会： 与正确伪代码相比 ，你少考虑了什么？下周堂上讨论各自的体会。这是一种很好的编程技能的训练和经验的积累，务必先做后对比。希望以后自己也常做类似练习。另一个分治的例子2017年春季通信网络理论基础24 36整数乘法都还记得小学老师教的吧？算法复杂度？CANWEDOBETTER？每个学算法的人都要让自己成为偏执狂。如何分治？a,
13、b, c, d都是 n/2位的整数。两个 递归 算法2017年春季通信网络理论基础25 36分解方式也有了，合并公式也有了，设计个递归吧？ALG#1 折半分解；递归计算 ac,ad,bc,bd；利用合并公式输出。 【 注： 4次递归 】合并公式ALG#2 折半分解；递归计算 ac,bd,(a+b)(c+d)；利用合并公式输出。 【 注： 3次递归 】Gauss Trick: 只用 3个递归输出同样可以计算合并公式。哪个更好？2017年春季通信网络理论基础26 36ALG#1 折半分解；递归计算 ac,ad,bc,bd；利用合并公式输出。 【 注： 4次递归 】ALG#2 折半分解；递归计算 a
14、c,bd,(a+b)(c+d)；利用合并公式输出。 【 注： 3次递归 】两个算法在递归调用之外做了哪些工作？画个递归树来求解？ 也行。但有个更好的办法。递归 式2017年春季通信网络理论基础27 36主方法 ：用来求解递归式的一种方法。 【 “Black Box”】递归式是什么？基于分治的递归算法的 RT，通常可以表达出递归式。T(n):规模为 n时，算法的操作次数上界。4 :递归调用的次数。 O(n):递归之外的 RT。MergeSort注意共同点：分解出来的 子问题规模相同 。主方法 (Master Method)2017年春季通信网络理论基础28 36主定理对数的底到底要不要出现？有时
15、必须要；有时不必。求解的例子 (1/2)2017年春季通信网络理论基础29 36复杂度？ 复杂度？ 这个算法你觉得奇怪吗？求解的例子 (2/2)2017年春季通信网络理论基础30 36复杂度？ 复杂度？ 高斯还是真的牛人啊。证 明主定理2017年春季通信网络理论基础31 36假定 n是 b的幂。 【 一般情况的证明思路类似 】基本思路：扩展 MergeSort的分析方法 递归树。Level0:最外层调用；问题的规模是 n。Level1:a个子问题， n/b递归树 第 j层的子问题数目？第 j层的子问题规模？第 j层总的 RT？总 RT？对 参数的理解2017年春季通信网络理论基础32 36a是什么？ 子问题数目的增长速率。每个子问题 RT的缩减速率。每层的 RT是一样的。 Me
