<<算法引论>> ------- 一种创造性方法
---读书笔记【美】Udi Mander
计算1314
苏帅豪
201321121109
Chapter 1: （引论）
广义地说，算法是按部就班解决一个问题或完成某个目标的过程。
数学归纳法其原理的主要思想是命题无须从什么都没有开始证明，可以通过先证明对于一个小的基本实例集命题是正确的，然后由?若对相对较小的命题实例成立则可导出较大的命题实例成立?的方式，来证明对所有实例来说命题都是成立的。因此它的基本思想是如何扩充一个解决方案而不是从零开始进行构造。
Chapter2: (数学归纳法) 显而易见与真知灼见水火不容。——伯特兰·罗素每次用归纳法证明都分成两步：归纳基础和规约。归纳基础一般都比较容易，偶尔也有不太简单的，但我们往往不太在意。归纳法证明的核心就是规约，有多种规约方法，其中最常用的就是把命题从N规约到N—1 ，从N+1规约到N也比较常见。强归纳法会把命题从N规约到比N小（但不一定是N-1）的一个或多个命题。其它变形还有从2N规约到N，以及逆向归纳法，也就是命题在N时的情况是由N+1的情况推出的，而归纳基础是个已被证明的无限集。规约的要点在于要完整保留原命题，不能在规约后的命题中加入多余的假设，除非这些假设是特别包含在归纳假设中的。
增量：
很明显，增量就是和我们平时的数学归纳法一样，特殊点的就是
证明起始条件；假设对于K，证明成立；用假设去证明对K+1，证明成立
证明的重点就这如何利用‘K’证明‘(K+1)’
当然也可以认为是利用某种性质去推广
其实这个就是动态规划和贪心的基本性质，最优子结构性质以及重叠子问题性质(贪心选择性质)中的最优子结构性质；
现在举个"不同"例子找多数元素(多数元素的定义：在给定有限个序列内，某元素的个数大于序列个数的1/2(比如 {1 2 3 3 3}中的3))
首先我们第一会想到枚举，很简单，时间复杂度为O(n^2)；最好的情况是一遍遍历就找到了:O(n) 最坏的情况是序列中没有多数元素：O(n^2) 平均情况:O(n^2)
现在让我们想下对于多数元素有什么性质，设序列元素个数为N，多数元素个数为m，
接下来给出一个很直接的性质(虽说很直接但是对我来说是不容易自己想出来的)：
性质1：删除序列中的两个不同的数，若存在多数元素，多数元素依然存在且不变。
现在我可以想出一个算法:
集合A:序列
循环：i：1->n-1
if(A[i]==A[i+1]||A[i]不存在) continue;
else delete A[i],A[i+1];
得到集合A`
很明显，集合A·中的元素一定相同
但是有个问题：集合中的元素不一定就是多数元素。
原因是性质1的前提是多数元素对于序列存在，我们可能会得到一个非法解
我们该怎么办，很简单，验证下最后得到的那个元素就行，
时间复杂度：O(n);
现在回过头看看我们的思路：
找到多数元素的性质，依次"增量"递减得到可能解，验证；
很明显找到性质是最关键的一步；
第二个例子，贪心；
双机调度问题：问题描述
给定n个作业，每个作业有两道工序，分别在两台机器上处理。一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。
一个作业只有在机器1上的处理完成以后才能由机器2处理。假设已知作业i在机器j上需要的处理时间为t[i,j]。流水作业调度问题就是要求确定一个
作业的处理顺序使得尽快完成这n个作业。
分析下：
若只有一个作业(a,，b1),明显时间为a1+b1;
若有两个作业(a1,b1),(a2,b2);
若(a1,b1)在前，则有时间T12=a1+b1+a2+b2-min(a2,b1);
若(a2,b2)在前，则有时间T21=a2+b2+a1+b1-min(b2,a1);
有上可得时间为Tmin=a1+b1+a2+b2-max{min(a2,b1),min(a1，b2)};
由此我们可以得到一个贪心的性质，(a1,b1)和(a2,b2)中的元素若min(a2,b1)>=min(a1，b2)则(a1,b1)放在(a2,b2)前面；反之(a2,b2)放在(a1,b1)前面；
根据这个性质我们对作业进行排序即得到最优工作序列；
PS：由于个人表述能力不行，所以这个例子还有一些思考量，所以请大家自己用笔在纸上写下就可以得到一样的结论。
例外这个问题有个很优美的算法 Johnson算法，基本原理与上面类似，但是把结论做得更漂亮些了，有兴趣的可以去看下证明过程；
这里给出Johnson算法:
对给定的任务进行如下排序：
得到序列A：s1[i]>=s1[j] 且以s1不减排序
序列B:s1[i] 最优调度即为A+B； 现在再回到数学归纳法上，回想如果我们得到K结论不足以证明?K+1?该怎么办？！ 一个很常用的思想就是加强结论； 例三：最大连续子序列和问题 问题描述：给出序列A，求连续子序列和最大，我们定空序列为0； 下面直接给数学归纳法的(思考)过程： 设序列中元素个数为n 若序列中元素个数n为1，则最大子序列和为:A[1]>0?A[1]:0; 假设对于子序列"K"(前k个元素的子序列)，得到最大子序列S=?A[i]...A[j]?(1<=i<=j<=k) 那么对于子序列"K+1",若S中的j=k+1，那么S'=S+A[k+1]>=S?S+A[k+1]:S; 若S中的j！=k+1，.... 这个，我们该怎么办呢，关于最大子序列S与A[k+1]我们找不到更多的联系； 那么我们加强下论证结果，加入一个最大尾子序列和(包括当前序列尾节点的最大子序列)：S.end=?A[m]...A[k]?(1<=m<=k) 明显若S.end<0时，我们可以将S.end=0; 现在我们重新证明下； 设序列中元素个数为n 若序列中元素个数n为1，则最大子序列和为:A[1]>0?A[1]:0;最大尾子序列和为：0+A[1]>0?0+A[1]:0; 假设对于子序列"K"(前k个元素的子序列)，得到最大子序列S=?A[i]...A[j]?(1<=i<=j<=k) 最大尾子序列S.end="A[m]...A[k]"(1<=m<=k) 那么对于子序列"K+1",最大子序列和为S>S.end+A[k]?S:S.end+A[k]; 最大尾子序列和为S.end+A[k]>=0?S.end+A[k]:0; 这样就可以得到我们熟悉的时间复杂度为O(n)的最大子序列和算法了。 首先给出时间复杂度的主方法; 给出这个的目的是一种指引，对于设计算法的指引，通过这个你可以看到怎么样设计一个算法它的时间复杂度更低； 例子四，最近点对问题 问题描述：给出二维平面内若干个点的坐标，求出欧式距离最小的点对； 这个问题的算法有种分治版本并且网上的证明很多，我只是想给出它的简单思想； 首先对所有点进行排序，按照x递增的顺序排序； 1，二分排序后的点；两边的点数目大致相等(这只是奇偶数问题) 2，对两边点进行递归求解子最小点对距离len1，len2，直至点的数目<=3直接进行求解；3，合并； 对于合并，如果我们枚举的话，根据上面的主方法得到时间复杂度为O(n^2)，这样还增加了问题的复杂性； 我们可以看到只有在划分线周围的点才可能比两边找到的子最近点对距离， 所以我们找到划分线两边距离d为min{len1，len2}的所有点； 若此时仍然枚举，时间复杂度还是为O(n^2); 接下来我就直接给出问题的正解，因为网上这类资料博客还是比较多的。 对于上一步得到的点，按照y不减排序，得到新的点序列，枚举每个点和每个点后6个的最小距离，更新最点点对距离； 根据主方法我们得到时间复杂度为O(nlogn) Chapter3: (算法分析) 仅仅望着树上的果实，而不去测量树的高度，是个愚人。——鲁夫斯 1.时间复杂度 （1）时间频度一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 （2）时间复杂度在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。 时间频度不同，但时间复杂度可能相同。如：T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。 按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶 O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...， k次方阶O(n k),指数阶 O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。（3）最坏时间复杂度和平均时间复杂度最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。 在最坏情况下的时间复杂度为T(n)=0(n)，它表示对于任何输入实例,该算法的运行时间不可能大于0(n)。平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。 指数阶0(2n)，显然，时间复杂度为指数阶0(2n)的算法效率极低，当n值稍大时就无法应用。 （4）求时间复杂度 【1】如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。 x=91; y=100; while(y>0) if(x>100) {x=x-10;y--;} else x++; 解答： T(n)=O(1)， 这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n没有? 没。这段程序的运行是和n无关的， 就算它再循环一万年，我们也不管他，只是一个常数阶的函数 【2】当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。 x=1; for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x++; 该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(5)的执行次数：则该程序段的时间复杂度为T(n)=O(n3/6+低次 项)=O(n3) 【3】算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。 在数值A[0..n-1]中查找给定值K的算法大致如下： i=n-1; while(i>=0&&(A[i]!=k)) i--; return i; 此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关: ①若A中没有与K相等的元素，则语句(3)的频度f(n)=n；②若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。 （5）时间复杂度评价性能 有两个算法A1和A2求解同一问题，时间复杂度分别是T1(n)=100n2，T2(n)=5n3。（1）当输入量n＜20时，有T1(n)＞T2(n)，后者花费的时间较少。（2）随着问题规模n的增大，两个算法的时间开销之比5n3/100n2=n/20亦随着增大。即当问题规模较大时，算法A1比算法A2要有效地多。它们的渐近时间复杂度O(n2)和O(n3)从宏观上评价了这两个算法在时间方面的质量。在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。 2.空间复杂度 一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。 （1）固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。 （2）可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部 分的空间大小与算法有关。 一个算法所需的存储空间用f(n)表示。S(n)=O(f(n)) 其中n为问题的规模，S(n)表示 空间复杂度。 预测一个算法的行为虽然并不困难，但也绝非易事。忽略细节而提取算法最重要的特 征。使用符号o是有帮助的，但是必须记住它只是一个初步的近似。另一方面，算法分析的 困难并不会阻碍算法的设计，获得算法效率的某些暗示，才是算法分析的本质。在许多情况 下，特别是使用递归算法时，我们可以得到一个递推关系。处理递推关系的首要任务，是考 察它前面的若干项，这可以使我们对此关系的行为有些感觉，虽然这有助于对解做出猜测， 但还不够。另一个有用的步骤是将递推关系多次展开，先猜测然后进行验证是求解递推关系 的一种较好的技巧，但它也仅仅是初步的技术，有时我们必须小心以免过度猜测，这时虽然 可得一个正确的上界，但结果太保守了。还有许多其他技巧就不一一提及了。幸运的是，实 际算法可能导致的一些递推关系，大部分已在本章进行了描述。在许多情况下，第一步通常 是假定n具有特定的形式，如n为2的幂，这已经够了。 Chapter4: (数据结构简介) 1. 数据结构式构造计算机算法的基础。 抽象数据类型是数据结构中一个非常有用的思想。数据结构分为静态和动态两种。数组 是静态数据结构。在使用数组前要先知道数组的大小，而且以后不能扩大，但是访问数组元 素的效率却很高。链表是动态的，大小可以随意调整，能够满足任意大小的需要。 如果存储的数据不依赖特别的结构，那么散列将值得考虑。如果在访问元素时除了关键 字外还需考虑其他因素，那么就不能用散列了。例如，假如我们想要查找散列表中的最小的 关键字，此时将不得不扫描整张表。 Chapter5: (基于归纳的算法设计) 基于归纳的算法思想类似于数学归纳法，方法要保证两点：第一、解决问题的一个 小规模事例是可能的（基础事例），第二、每个问题的解答都可由更小规模问题的解答构造 出来（归纳步骤）。 1、如果原始问题的规模为n，假设问题规模为n-1时的求解释已知的，那 么只要求出从n->n-1的过程即可。 2、如果所求的问题，有如下的性质：[P and Q]( style="word-wrap: break-word;"> [P and Q](n)。 需要注意：问题规模缩小时，必须保证子问题和原问题满足的条件必须一 致；如果用更强的归纳，所使用的条件Q要证明。 1、多项式求值 问题给定一串实数a n,a n-1,...,a1,a0,以及一个实数x，计算多项式P n(x) = a n x n + a n-1x n-1+ ... + a1x ＋a 两种归纳假设的思路：a 、P n-1(x) = a n-1x n-1 + a n-2x n-2 + ... + a 1x ＋a 0（假如n-1规模已知） Pn(x) = anx n + Pn-1(x) （问题规模n->n-1） b 、P'n-1(x) = anx n-1 + an-1x n-2 + ... + a1 （假如n-1规模已知） Pn (x) = x.P'n-1(x) + a0（问题规模n->n-1） 明显思路b 的算法好于a 。 2、最大到处子图 归纳思路： [全局观] 首先，考虑顶点数小于n 的情况，如果n<=k ，那么即使是完全图，也无法满足要求，如果n=k+1，只有完全图才能满足要求。（问题的终止条件） [归纳假设] 然后，考虑n>k+1的情况，首先假设顶点数为n-1的情况是已知最大导出子图的。（假如n-1规模已知） 如果顶点的度 说明：1、处理顶点的 2、如果问题改成每个顶点的度小于或等于k ，那么问题将变成NP ，不能用同样的方法求解。 3、寻找一对一映射 归纳思路： a、对于包括n-1个元素的集合，如何求解是已知的（假如n-1规模已知） b、没有被任何元素映射的元素i 不可能属于集合S（换句话被映射次数为0的元素不可能属于集合S），要把元素i 删除，同时要删除f(i)元素被映射的次数。（规模n->n-1） 4、社会名流问题 归纳思路： a、对于包括n-1个元素的集合，如何求解是已知的（假如n-1规模已知） b、Know[i,j]=1，i不是名人去掉i，如果Know[i,j]=0，j不是名人去掉 j（规模n->n-1） 最后的检验：当问题规模为1时，检验这个这个结果是否满足要求，Know[i,ca] = 1(i>=1 && i<=n && i !=ca) 以及 Know[ca,j] = 0(j>=1 && j<=n && j !=ca) 5、在二叉树中计算平衡因子 归纳思路： 我们已知如何计算节点数小于n的二叉树的全部节点的平衡因子。 更强的归纳假设： 已知如何计算节点小于n的二叉树的全部节点的平衡因子和高度。（假如n-1规模已知） 根节点的平衡因子只与子节点的高度有关，所以提出更强的假设，虽然多求了高度，但简化了计算。（规模n->n-1） 通过把问题的一个实例归约到一个或多个较小规模的实例，可以使用归纳原理来设计算法。如果归约总能实现，并且基础情况可被解决，则算法可以通过归纳进行设计。可以用多种方式来归约问题的规模。然而，不是所有归约都有同样的效率，因此要考虑所有归约的可能性。特别是，考虑不同的归约次序是值得一试的。我们看到了先处理最大元素较好的例子，同时，，也看到了先处理最小元素较好的例子，还有从中间开始处理的例子，也看到对 树进行归纳时先删除跟的例子，以及先删除叶子的例子。由于归约只能改变问题的规模，并不改变问题本身，所以应该寻找尽可能独立的小规模的子问题。例如，在一些项目中寻找某些次序的问题可以归约到按次序寻找项目的问题；剩余项目的相关次序与第一个项目无关。 Chapter6：（序列和集合的算法） 1.选择排序 基本思想： 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 2.直接插入排序 基本思想： 每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。 3.冒泡排序 基本思想： 依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。 4.Shell排序 基本思想： 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2 该方法实质上是一种分组插入方法。 5.堆排序 基本思想： ①先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区 ②再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key ③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n- 1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。…… 直到无序区只有一个元素为止。 6.快速排序 基本思想： 快速排序（Quicksort）是对冒泡排序的一种改进。 它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 7.归并排序 基本思想： 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 归并操作的工作原理如下： 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 设定两个指针，最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 重复步骤3直到某一指针达到序列尾 将另一序列剩下的所有元素直接复制到合并序列尾 8.基数排序 基本思想： 基数排序法又称?桶子法?（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些?桶?中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。 最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。 最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。 数据压缩是节省存储空间的重要技术。一般把待压缩的文件看成字符串，压缩后的文件越小就越好，但必须能从中还原出压缩前的文件。数据压缩技术十分有用，比如有些很少访问的文件，其存储代价远远高于压缩和解压的开销。数据压缩技术在通信方面也很重要。有时发送文件的代价比处理文件本身还要大。 Chapter7: (图算法) 图常被用于对象之间关系的建模。由于大多数算法需要对完整的输入进行检查，所以图算法涉及到的第一个问题通常是图的遍历。DFS特别是适合图的递归算法，而BFS通常需要更多的空间。优先搜索常用于计算单源最短路径。优先搜索比正规搜索的开销更大，它对涉及加权图的优化问题比较有用。回路通常会对图算法造成较大的困难。所以，关于树或者有向非循环图的算法通常比较容易设计，并且执行得也很快。要意识到，即使一个边数很少 的图也可能有多个不同的回路。在一个图中，若算法需要检查所有的或者大部分回路，则算法会非常慢。图分解是非常有用的，幸运的是，它的开销通常并不昂贵。书中给出的分解包括连通分支、双连通分支和强连通分支。基础分解可使我们假定某些性质的存在，即使给定的图并没有这些性质。另一个对图算法有用的技术是归约由于图可以用矩阵表示，从而在图和矩阵算法之间有着自然的关系。网络流量问题和匹配问题是进行归约的好例子。归约也能帮助我们确定一个问题是否是困难的。名为NP完全问题，它也许不能用最坏情况下运行时间是输人规模多项式的算法来解决这个类包含许多图问题有时候，容易的问题与难解问题之间的差别是很微小的。例如，我们已经看到一个有效算法，它能判定有向图是否包含一个奇数长度的闭链;而同样的问题再加上额外的约束，即要求闭链包含 指定的顶点(或者边)，则此问题是NP完全的。理解并拓展对这种差异的直觉很重要。 Chapter8:(几何算法) 归纳假设的基础情况很容易，为了推广这个假设，需要处理第(k+1)个端点，分为以下3种情 况: 1.第(k+l)个端点是一条水平线的右端点。在这种情况下，只要简单地将这条线从候选线的 集合中删除即可。正如先前所说，只有考虑竖直线时才检测交点，删除这条水平线并不会 遗漏交点。由此，该步推广了归纳假设 2第(k+l)个端点是一条水平线的左端点在这种情况下，我们将这条线添加人候选线的集合。因为这条线的右端点还未曾遇到，所以这条线不应被删除。根据上述论证，这是推广 归纳假设的正确方法。 3.第(k+1)个端点是一条竖直线。这是算法的主要部分，通过检查候选线集合中所有水平线的y坐标和该竖直线的y坐标，可以找到所有涉及该竖直线的交点。 从某种意义_上说，由于我们习惯于观察和处理几何对象，几何算法看似比图算法更具体直观，但是表象有时容易误导:处理大量对象与观察小规模的图形是不同的，我们必须小心不要被脑海中的图形所误导。还必须处理许多特例，并确保己经全部将它们考虑在内。判断点是否在多边形内部的算法就是一个典型的例子.此外我们也很容易忽略可能产生的特例因此，在设计几何算法时，一定要特别小心谨慎:设汁〔离散)几何算法的技术与先前章节所学的技术很相似归纳法在其中起了很重要的作用，基于归纳法的扫描线技术在一些几何算法中很常见，分治法同样也很常见:几何算法倾向于使用复杂的数据结构。由此发展了许多复杂且具有独创性的数据结构，这里并没有涉及任何这类特别的数据结构。 Chapter9 (代数和数值算法) 本章所给出的算法只是已知的代数和数值算法中的一些例子，由此再次说明直接算法并不一定是最佳的。非直观算法可用来解决看似简单的问题，而Strassen算法则是其中最显著的例子之一。本章还给出了一些使用归纳法的例子，特别是那些使用分治法的算法的设计。4个俄国人算法提出了一项并不基于归纳法的有趣技术，其主要思想是计算某些项的各种可能组合，即使所有组合并非都用得上。在计算全部(或许多)组合的开销远小于分开计算每一种组合的情况下，这项技术非常有用。另一项技术是在问题之间使用归约的方法，它通常可用来解决涉及矩阵的问题。 Chapter 10 (归约) 假设有一个较复杂的问题p，而它看起来与一个已知问题Q很相似，尽管可能存在其 他方法.我们也可以尝试挖掘或借用解决Q的一些方法，并应用于p可以试着在两个问题间找到一个归约(reduction)或者变换(transformation )。非严格地说，归约是使用解决其他间题的‘黑盒?来解决另一个问题二取决于问题解决的先后，归约可以达到两个目标之一(也就是说。用哪个黑盒来解决哪个问题)。如果我们已知Q的算法，那么就可以把使用了Q的黑盒的P的解决方法转化成一个p的算法。另一方面，如果p是一个已知的难题，或者如果知道p的下限，那么同样的下限也可能适用于Q。前一个归约用于获取P的信息;而后者则用于获取Q的相关信息。在问题间寻找相似点总是个好主意。通过学习两个问题间的异同点.常能获取对两个问题的内在领悟。给定一个新问题，第一个念头应该是(几乎在所有情况下):这个问题与已知的某问 题相似吗?有时只有经过复杂的归约，两个间题的相似处才变得明了;矩阵与图算法的归约淤得特别有趣。本章中我们己经看到一些归约的例子，在下一章将看到更多的例子.虽然很重要，但线性和整数归约在本章还是介绍得过于简要，有兴趣的读者应该详细而系统地进行学习。 Chapter 11 迄今为止多项式时间的算法还是个未知数，其中一些问题的高效算法仍有待发现，但我们强烈怀疑许多问题不可能有高效的解决方法、希望能够识别这些问题，从而不必浪费时间去寻找不存在的算法在这一章，我们将探讨如何处理不被认为是属于P的问题，尤其是一类被称为NP完全问题的特殊例子二将这些问题归为一类是因为它们在如下意义下是等价的，即某个NP完全问题存在着高效算法当且仅当所有的NP问题都存在着高效算法。普遍的观点是NP完全问题不存在高效算法，但却没有人能够找到该信念的证明即使存在解决NP 完全问题的高效算法，但由于研究者寻求了许多年都未曾发现，它们也一定非常复杂迄今为止，数以百计的问题被证明是NP完全的。 NP完全问题是一个优雅的理论，该理论计我们能识别出那些不太可能存在多项式时间算法的问题。但是证明给定问题是NP完全的并不能消除这个问题。我们仍然需要解决它。解决NP完全问题的技术与先前所看到的技术有时是不同的。我们不能用多项式时间精确而彻底地解决一个NP完全问题。因此必须采取折中的方式。通常折中的考虑因素有最优性健壮性、高效性以及解的完备性等，每者都会有一些相应的牺牲.相同算法在不同场景下使用将会有不同的折中。 Chapter 12 共享存储器计算机包含若干处理器和一个共享存储器。我们假定一个计算可分为若干步，每个处理器在每一步可以对它持有的数据进行一次操作，也可从共享存储器中读取数据，或将数据写人共享存储器。实际上，每个处理器可能也有自己的局部处理器，但我们假定所有处理器都是全局的。共享处理器模型的区别在于内存冲突处理方式的不同不允许同时读和同时写的EREW模型不允许多于一个处理器同时访问同一内存位置;允许同时读但不允许同时写的数据;CREW模型允许多个处理器同时读取内存的同一位置，但仅允许一个处理器写人而允许同时读和同时写的CRCW模型对内存冲突未提出任何限制。 由于并行算法的设计远比串行算法的设计复杂，因此最好是充分利用积木构件。并行前缀就是一种强有力的积木构件，甚至曾被建议作为一种基本机器指令，同样的构件还有基于排列的路由操作。要预料哪一种并行结构在未来将居统治地位还为时过早。然而，有必要给出对许多模型来说都通用的设计技术。当然还存在更多的其他技术:加倍法、并行分治法.流水线以及欧拉遍历技术。归纳法在这里再次起到了重要的作用。 一 1.循环赛日程表问题的相关叙述。 2.算法运行时所需要占用的存储空间有？ 3.动态规划法的求解步骤 4.解空间树是排列树的问题有。 5.分治法的步骤 6.就会场安排问题，贪心法的最佳贪心策略 7.快速排序法基准元素的选取方法 8.满足满m叉树的问题有？ 9.分支限界法的解题步骤 10.事前分析法相关的影响因素有 11.用分治法求解的问题一般需要具备一些特征，主要有？ 二 1．给定一个有向带权图G=(V，E)，其中每条边的权是一个非负实数，另外，给定V中的一个顶点，称为源点。现在要计算从源点到所有其它各个顶点的最短路径长度，这里的路径长度是指路径上经过的所有边上的权值之和，这个问题通常称为单源最短路径问题。 2．采用回溯法可以求解0-1背包问题，其解空间的形式为：（x1,x2,…,xn）或n 元组。 3．当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为排列树。 4．一个正在生成孩子的结点称为扩展结点。 5．子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。 6．当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素取值的一种组合，这类问题的解空间树称为满m叉树。 7．一个自身已生成但其孩子还没有全部生成的结点称为活结点 8．回溯法中，对于问题的一个实例，解向量满足显约束的所有n元组构成了该实例的一个解空间 9．分支限界法有两种：队列式分支限界法和优先队列式分支限界法。 10．分支限界法采用的是宽度优先搜索。 11．时间复杂性的度量方法通常有两种：事后统计法和事前分析估算法 12．一个所有孩子已经生成的结点称做死结点 13．在最小生成树的生成方法中，Kruskal算法从边的角度出发，每一次将图中的权值最小的边取出来，在不构成环的情况下，将该边加入最小生成树。 三 1．分治法字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同子问题，子问题相互独立，如果子问题还是不容易解决，再把子问题分成更小的子问题…，直到最后各个子问题可以简单地直接求解，对各个子问题递归求解，将子问题的解进行合并即得原问题的解。 2．动态规划法要求将大问题分解成规模较小的子问题，经分解得到的各个子问题往往不是相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。采 1. 贪心算法和动态规划算法有什么共同点和区别？它们都有那些优势和劣势？ 共通点：动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解 区别：贪心算法中，作出的每步贪心决策都无法改变，每一步的最优解一定包含上一步的 最优解，而上一部之前的最优解则不作保留。 动态优化算法，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。但它需要计算之前所有情况花费，更加耗费空间。 贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编 码和执行过程中都有一定的速度优势。贪心算法是只是找局部最优解，不一定是全局最优解。 2. 试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？ 二者都是在解空间树里搜索问题的可靠解或最优解，但是搜索的方式不同，回溯法采用深 度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点，然后，从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。可以看出，回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解。 3. 何谓最优化原理？采用动态规划算法必须满足的条件是什么？动态规划算法是通过什 么问题的什么特性提高效率的？ 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构性质，子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率 4. 什么是多项式时间算法？ 若存在一个常数C，使得对于所有n>=0，都有|f(n)| <= C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。 时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。 一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并 将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。。 《数据结构》必须掌握的知识点与算法 第一章绪论 1、算法的五个重要特性（有穷性、确定性、可行性、输入、输出） 2、算法设计的要求（正确性、可读性、健壮性、效率与低存储量需求） 3、算法与程序的关系： （1）一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。 （2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。 （3）一个算法若用程序设计语言来描述，则它就是一个程序。 4、算法的时间复杂度的表示与计算（这个比较复杂，具体看算法本身，一般关心其循环的次数与N的关系、函数递归的计算） 第二章线性表 1、线性表的特点： （1）存在唯一的第一个元素；（这一点决定了图不是线性表） （2）存在唯一的最后一个元素； （3）除第一个元素外，其它均只有一个前驱（这一点决定了树不是线性表） （4）除最后一个元素外，其它均只有一个后继。 2、线性表有两种表示：顺序表示（数组）、链式表示（链表），栈、队列都是线性表，他们都可以用数组、链表来实现。 3、顺序表示的线性表（数组）地址计算方法： （1）一维数组，设DataType a[N]的首地址为A0，每一个数据（DataType类型）占m个字节，则a[k]的地址为：A a[k]＝A0+m*k（其直接意义就是求在数据a[k]的前面有多少个元素，每个元素占m个字节） （2）多维数组，以三维数组为例，设DataType a[M][N][P]的首地址为A000，每一个数据（DataType 类型）占m个字节，则在元素a[i][j][k]的前面共有元素个数为：M*N*i+N*j+k，其其地址为： A a[i][j][k]＝A000+m*(M*N*i+N*j+k)； 4、线性表的归并排序： 设两个线性表均已经按非递减顺序排好序，现要将两者合并为一个线性表，并仍然接非递减顺序。可见算法2.2 5、掌握线性表的顺序表示法定义代码，各元素的含义； 6、顺序线性表的初始化过程，可见算法2.3 7、顺序线性表的元素的查找。 8、顺序线性表的元素的插入算法，注意其对于当原来的存储空间满了后，追加存储空间（就是每次增加若干个空间，一般为10个）的处理过程，可见算法2.4 9、顺序线性表的删除元素过程，可见算法2.5 10、顺序线性表的归并算法，可见算法2.7 11、链表的定义代码，各元素的含义，并能用图形象地表示出来，以利分析； 12、链表中元素的查找 13、链表的元素插入，算法与图解，可见算法2.9 14、链表的元素的删除，算法与图解，可见算法2.10 15、链表的创建过程，算法与图解，注意，链表有两种（向表头生长、向表尾生长，分别用在栈、队列中），但他们的区别就是在创建时就产生了，可见算法2.11 16、链表的归并算法，可见算法2.12 17、建议了解所谓的静态单链表（即用数组的形式来实现链表的操作），可见算法2.13 18、循环链表的定义，意义 19、循环链表的构造算法（其与单链表的区别是在创建时确定的）、图解 算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 5. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_有穷性__,_确定性_,_可行性_,_ （0个或多个）输入__,_ （1个或多个）_输出_。 2.算法的复杂性有__时间复杂性__和__空间复杂性__之分，衡量一个 算法好坏的标准是__时间复杂度高低___。 3.某一问题可用动态规划算法求解的显著特征是___该问题具有最优 子结构性质___。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_{A,B,C,D}_。{BABCD}或{CABCD}或{CADCD｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含_问题的一个（最优）解_。 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题_，先求解_子问题__，然后从这些_子问题_的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为__回溯法__。 8.0-1背包问题的回溯算法所需的计算时间为__O（n2n）__,用动态规划算法所需的计算时间为_O（n）__。o(min{nc,2n}) 9.动态规划算法的两个基本要素是_最优子结构_和_重叠子问题 ___。 10.二分搜索算法是利用__动态规划法__实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 1、解：（1）找出最优解的性质，并刻画其结构特征； （2）递归地定义最优值； （3）以自底向上的方式计算出最优值； （4）根据计算最优值时得到的信息，构造最优解。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解 2.流水作业调度问题的johnson算法的思想。 2、解：①令N1={i|a i=b i}；②将N1中作业按a i 的非减序排序得到N1’，将N2中作业按b i的非增序排序得到N2’； ③N1’中作业接N2’中作业就构成了满足Johnson法则的最优调度。 3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 3、解：步骤为：N1={1，3}，N2={2，4}； N1’={1，3}， N2’={4，2}； 最优值为：38 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 算法设计与分析的复习要点 第一章：算法问题求解基础 算法是对特定问题求解步骤的一种描述，它是指令的有限序列。 一．算法的五个特征： 1．输入：算法有零个或多个输入量； 2．输出：算法至少产生一个输出量； 3．确定性：算法的每一条指令都有确切的定义，没有二义性； 4．可行性：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现； 5．有穷性：算法必须总能在执行有限步之后终止。 二．什么是算法？程序与算法的区别 1．笼统地说，算法是求解一类问题的任意一种特殊的方法；较严格地说，算法是对特定问题求解步骤的一种描述，它是指令的有限序列。 2．程序是算法用某种程序设计语言的具体实现；算法必须可终止，程序却没有这一限制；即：程序可以不满足算法的第5个性质“有穷性”。 三．一个问题求解过程包括：理解问题、设计方案、实现方案、回顾复查。 四．系统生命周期或软件生命周期分为： 开发期：分析、设计、编码、测试；运行期：维护。 五．算法描述方法：自然语言、流程图、伪代码、程序设计语言等。 六．算法分析：是指对算法的执行时间和所需空间的估算。算法的效率通过算法分析来确定。 七．递归定义：是一种直接或间接引用自身的定义方法。一个合法的递归定义包括两部分：基础情况和递归部分； 基础情况：以直接形式明确列举新事物的若干简单对象； 递归部分：有简单或较简单对象定义新对象的条件和方法 八．常见的程序正确性证明方法： 1.归纳法：由基础情况和归纳步骤组成。归纳法是证明递归算法正确性和进行算法分析的强有力工具； 2.反证法。 第二章：算法分析基础 一．会计算程序步的执行次数（如书中例题程序2-1,2-2,2-3的总程序步数的计算）。二．会证明5个渐近记法。（如书中P22-25例2-1至例2-9） 三．会计算递推式的显式。（迭代法、代换法，主方法） 四．会用主定理求T(n)=aT(n/b)+f(n)。（主定理见P29，如例2-15至例2-18）五．一个好的算法应具备的4个重要特征： 1.正确性：算法的执行结果应当满足预先规定的功能和性能要求； 2.简明性：算法应思路清晰、层次分明、容易理解、利于编码和调试； 3.效率：算法应有效使用存储空间，并具有高的时间效率； 4.最优性：算法的执行时间已达到求解该类问题所需时间的下界。 六．影响程序运行时间的主要因素： 1.程序所依赖的算法； 2.问题规模和输入数据规模； 3.计算机系统性能。 七．1.算法的时间复杂度：是指算法运行所需的时间； 一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ） 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。 填空 1．直接或间接地调用自身的算法称为 递归 。 2．算法的复杂性是 算法效率 的度量，是评价算法优劣的重要依据。 3．以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。 4．回溯法解题的显著特点是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为 o(h(n)) 。 5．人们通常将问题的解决方案分为两大类：一类是可以通过执行若干个步骤就能得出问题 6．算法就是一组有穷的 规则 ，它们规定了解决某一特定类型问题的 一系列运算 。 7．在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基本计算模型是 随机存取机、 随机存取存储程序机 、 图灵机 。 8．快速排序算法的性能取决于 划分的对称性 。 9．计算机的资源最重要的是 内存 和 运算 资源。因而，算法的复杂性有时间 和 空间 之分。 10．贪心算法总是做出在当前看来 最优 的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的 局部最优解 。 11．许多可以用贪心算法求解的问题一般具有2个重要的性质： 最优子结构的 性质和 贪心选择的 性质。 12．常见的两种分支限界法为 队列式 和 优先队列式 。 13．解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中需要排序的是 回溯法 ，不需要排序的是 动态规划和分支限界法 。 14．f ( n ) = 6 × 2n + n 2，f(n)的渐进性态f ( n ) = O ( 2^n )。 15．对于含有n 个元素的排列树问题，最好情况下计算时间复杂性为 ，最坏情况下计算时间复杂性为 n! 。 16．在忽略常数因子的情况下，O 、Ω和Θ三个符号中， Θ 提供了算法运行时间的一个上界。 17．回溯法的求解过程，即在问题的解空间树中，按 深度优先 策略从根结点出发搜索解空间树。 18．分支限界法的求解过程，即在问题的解空间树中，按 广度优先 策略从根结点出发搜索解空间树。 19．多项式10()m m A n a n a n a =+ ++的上界为 2^n 。 20．用分支限界法解布线问题时，对空间树搜索结束的标志是 活结点表为空 。 21．使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N 皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进 ·算法是指解决问题的方法和过程。算法是由若干条指令组成的有穷序列。 ·算法特性：输入、输出、确定性、有限性（执行时间和执行次数）（有五个空再加上可行性）。 ·程序是算法用某种程序设计语言的具体实现，程序可不满足有限性的特性。 ·程序调试只能证明程序有错，不能证明程序无错误! ·算法复杂性= 算法所需要的计算机资源。 ·算法的复杂性取决于：(1)求解问题的规模N；(2)具体的输入数据I；(3)算法本身的设计A。·可操作性最好且最有实际价值的是最坏情况下的时间复杂性。 第二章递归与分治策略 二分搜索技术：O（logn）大整数乘法：O（n log3）=O（n1.59）Strassen矩阵乘法：O（n log7）=O(n2.81) 棋盘覆盖：O（4k）合并排序和快排：O（nlogn）线性时间选择：O(n) 最接近点对问题：O(nlogn) 循环赛日程表：O(n2) ·分治法思想：将一个难以解决的问题分割成一些规模较小的相同问题，以便逐个击破，分而治之。边界条件与递归方程是递归函数的两大要素。 递归优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 ·分治法时间复杂度分析：T(n)<= O(1) n=n0 aT(n/b)+f(n) n>n0 若递归方式为减法：T(n) = O(a n) 若递归方式为除法： f(n)为合并为原问题的开销：f(n)为常数c时：T(n)=O(n p) f(n)为线性函数：O(n) ab,p=log b a f(n)为幂函数n x时：O(n x) a 湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14 计算机算法设计与分析复习题一、填空题1、一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有时间复杂性和空间复杂性之分。2、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致相同。3、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O （1），在最坏情况下，搜索的时间复杂性为O（logn）。4、已知一个分治算法耗费的计算时间T(n)，T(n)满足如下递归方程： n2O(1) T(n)2T(n/2)O(n)n2解得此递归方可得T(n)= O（）。 nlogn5、动态规划算法有一个变形方法备忘录方法。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。递归的二分查找算法在divide阶段所花的时间是 O(1) ，conquer阶段6．所花的时间是 T(n/2) ，算法的时间复杂度是 O( log n) 。7．Prim算法利用贪心策略求解最小生成树问题，其时间复杂度是 2O(n) 。8．背包问题可用贪心法，回溯法等策略求解。39．用动态规划算法计算矩阵连乘问题的最优值所花的时间是 O(n) ，子2问题空间大小是 O(n) 。10．图的m着色问题可用回溯法求解，其解空间树中叶子结点个数是nm ，解空间树中每个内结点的孩子数是 m 。11．单源最短路径问题可用贪心法、分支限界等策略求解。12、一个算法的优劣可以用（时间复杂度）与（空间复杂度）与来衡量。 13、回溯法在问题的解空间中，按（深度优先方式）从根结点出发搜索解空间树。 14、直接或间接地调用自身的算法称为（递归算法）。 15、记号在算法复杂性的表示法中表示（渐进确界或紧致界）。 16、在分治法中，使子问题规模大致相等的做法是出自一种（平衡(banlancing)子问题）的思想。 17、动态规划算法适用于解（具有 1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一 第一章概述 算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。 算法的特征： 可终止性：算法必须在有限时间内终止； 正确性：算法必须正确描述问题的求解过程； 可行性：算法必须是可实施的； 算法可以有0个或0个以上的输入； 算法必须有1个或1个以上的输出。 算法与程序的关系： 区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束； 程序可以没有输出,而算法则必须有输出； 算法是面向问题求解的过程描述，程序则是算法的实现。 联系：程序是算法用某种程序设计语言的具体实现； 程序可以不满足算法的有限性性质。 算法描述方式：自然语言，流程图，伪代码，高级语言。 算法复杂性分析： 算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。 算法复杂性度量： 期望反映算法本身性能，与环境无关。 理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响）。 一般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单位的开销作为标准。 算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F(N, I, A)。 第二章递归与分治 分治法的基本思想： 求解问题算法的复杂性一般都与问题规模相关，问题规模越小越容易处理。 分治法的基本思想是，将一个难以直接解决的大问题，分解为规模较小的相同子问题，直至这些子问题容易直接求解，并且可以利用这些子问题的解求出原问题的解。各个击破，分而治之。 分治法产生的子问题一般是原问题的较小模式，这就为使用递归技术提供了方便。递归是分治法中最常用的技术。 使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。 分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。（这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。） 递归的概念： 华南农业大学期末考试试卷（A卷） 2008学年第一学期考试科目：算法分析与设计 考试类型：（闭卷）考试时间：120分钟 学号姓名年级专业 一、选择题（20分，每题2分） 1.下述表达不正确的是。 A．n2/2 + 2n的渐进表达式上界函数是O(2n) B．n2/2 + 2n的渐进表达式下界函数是Ω(2n) C．logn3的渐进表达式上界函数是O(logn) D．logn3的渐进表达式下界函数是Ω(n3) 2.当输入规模为n时，算法增长率最大的是。 A．5n B．20log2n C．2n2D．3nlog3n 3.T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是。A．T（n）= T（n – 1）+1，T（1）=1 B．T（n）= 2n2 C．T（n）= T（n/2）+1，T（1）=1 D．T（n）= 3nlog2n 4.在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨 牌的个数是。 A．（4k– 1）/3 B．2k /3 C．4k D．2k 5.在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算法 对n个元素进行划分，应如何选择划分基准？下面答案解释最合理。A．随机选择一个元素作为划分基准 B．取子序列的第一个元素作为划分基准 C．用中位数的中位数方法寻找划分基准 D．以上皆可行。但不同方法，算法复杂度上界可能不同 6. 现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在 才能使到邮局到这9个村庄的总距离和最短。 A ．（4.5，0） B ．（4.5，4.5） C ．（5，5） D ．（5，0） 7. n 个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水， 水流恒定。如下 说法不正确？ A ．让水桶大的人先打水，可以使得每个人排队时间之和最小 B ．让水桶小的人先打水，可以使得每个人排队时间之和最小 C ．让水桶小的人先打水，在某个确定的时间t 内，可以让尽可能多的人打上水 D ．若要在尽可能短的时间内，n 个人都打完水，按照什么顺序其实都一样 8. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分 别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 。 A ．问题规模相同，问题性质相同 B ．问题规模相同，问题性质不同 C ．问题规模不同，问题性质相同 D ．问题规模不同，问题性质不同 9. 对布线问题，以下 是不正确描述。 A ．布线问题的解空间是一个图 B ．可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定 C ．采用广度优先的标号法找到从起点到终点的布线方案（这个方案如果存在的话）不一定是最短的 D ．采用先入先出的队列作为活结点表，以终点b 为扩展结点或活结点队列为空作为算法结束条件 10. 对于含有n 个元素的子集树问题，最坏情况下其解空间的叶结点数目为 。 A ．n! B ．2n C ．2n+1-1 D ． ∑=n i i n 1 !/! 答案：DACAD CACCB 复习 一、简答题（每小题5分，选答2题，共10分） 1. 什么是算法？试说明算法设计分析过程的一般框架和主要步骤。 2. 简述非递归算法时间效率分析的通用方案。 3. 简述递归算法时间效率的通用方案。 4. 简述蛮力法、分治法、减治法，变治法、时空权衡、动态规划、贪婪技术、迭代改进八种算法设计技术中至少三种技术基本思想或原理。 二、分析题（每小题10分，共20分） 1. 考虑下面的算法。P52 算法Mystery(n) //输入：非负整数n S=0 for i ← 1 to n do S ← S + i*i Return S a.该算法求的是什么？ b.它的基本操作是什么？ c.该基本操作执行了多少次？ d.该算法的效率类型是什么？ 2. 考虑下面的递归算法。P52 算法Secret(A[0..n-1]) //输入：包含n个实数的数组A[0..n-1] minval ← A[0]; maxval ← A[0] for i ←1 to n-1 do if A[i] < minval minval ← A[i] if A[i] > maxval maxval ← A[i] return maxval – minval a.该算法求的是什么？ b.它的基本操作是什么？ c.该基本操作执行了多少次？ d.该算法的效率类型是什么？ 3. 考虑下面的递归算法P59 算法Q(n) //输入：正整数 if n=1 return 1 else return Q(n-1) + 2*n -1 a. 建立该函数值的递推关系并求解，以确定该算法计算的是什么； b. 建立该算法所做的乘法运算次数的递推关系并求解； c. 建立该算法所做的加减运算次数的递推关系并求解。 三、算法设计题（每小题10分，共20分） 1. 应用快速排序对序列E，X，A，M，P，L，E按照字母顺序排序。并画出相应的递归调 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型： C 卷 考试时量： 120 分钟 题号 一 二 三 四 五 总分 统分人 得 分 阅卷人 一、填空题（每小题 3 分，共计 30 分） 1. 用 O 、Ω和θ表示函数 f 与 g 之间的关系 ______________________________ 。 f n n lo g n g n log n 1, n 1 2. 算法的时间复杂性为 f (n) n ，则算法的时间复杂性的阶 8 f (3n / 7) n, 2 为__________________________ 。 3. 快速排序算法的性能取决于 ______________________________ 。 4. 算法是 _______________________________________________________ 。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的 是_________________________ 。 6. 在算法的三种情况下的复杂性中， 可操作性最好且最有实际价值的是 _____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越 ___________，结果就越有价值。 。 8. ____________________________ 是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。算法设计与分析复习资料1
中科院陈玉福计算机算法设计与分析期末简答题答案
考研数据结构必须掌握的知识点与算法-打印版
算法设计与分析考试题及答案
算法设计与分析报告考试题(自测)
算法设计与分析试卷(2010)
最新算法设计与分析复习要点(1)
算法设计与分析复习题目及答案
计算机算法设计与分析期末考试复习题
《算法设计与分析》复习题(汇编)
算法设计与分析复习要点
算法设计与分析试卷及答案
2015算法设计与分析考试复习刚要习题
算法设计与分析期末试题答案解析
算法分析与设计知识点总结
算法设计与分析课程期末试卷-A卷(自测 )
算法设计与分析期末总复习
算法设计与分析试卷及答案.doc
相关主题
文本预览