计算机算法设计与分析.doc

计算机算法设计与分析（书要整体看看再结合老师画的重点）第一章1.算法：是在有限步骤内求解某一问题所使用的一组定义明确的规则。 程序：是算法用某种程序设计语言的具体实现。1. 算法评定标准：时空的观点标准1 算法在计算机上的执行的时间最短。标准2 算法所需要的存储空间最小。发展的观点 标准3 算法的适应性强。设计的观点 标准4 算法的设计时间少。交流的观点 标准5 算法容易理解。2. 时间复杂性论：原因： 所有关于时间复杂性增长的阶的定义和渐近界的讨论都可移植到空间复杂性的讨论中。 算法的空间复杂性相对简单，它不可能超过运行时间的复杂性，因为写入每一个内存单元都至少需要一定的时间。对于一个相同的输入I，S(N)=O(T(N)。 空间复杂性降低到一定程度时会大幅度增加时间复杂性，而时间复杂性的降低一般对空间复杂性不会有太大影响。例： 求两个n阶矩阵的乘积C=AB的算法及其时间复杂性。定义矩阵A n，B n，C nfor i 0 to n 频度：n+1for j 0 to n 频度：n（n+1） Cij = 0; 频度：n2for k 0 to n 频度：n2(n+1) Cij = Cij + Aik * Bkj; 频度：n3 end for end forEnd for时间复杂性T(n) = n+1+n (n+1) + n2 + n2(n+1) + n3 = 2n3+3n2+2n+1上界的阶越低则评估越有价值。 下界的阶越高，则评估精度越高，也就越有价值。 T(n)大概有三种计算方法：计算迭代次数（循环结构的执行次数）计算基本运算的频度使用递归方程（多用于递归算法）第二章1.并非所有递归函数都能找到其非递归的定义。2.分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。原理：递归地解这些子问题，然后将各子问题的解合并得到原问题的解。分治法的适用条件：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题；利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。（而动态规划法适合各子问题不独立时，在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算 ）3. 棋盘覆盖法：算法描述：chessBoard(tr, tc, dr, dc, size)/tr:棋盘左上角方格的行号；tc:棋盘左上角方格的列号；dr:特殊方格所在行号；dc:特殊方格所在列号；size:棋盘规格；tile是全局变量，初值为0。过程 chessBoard(tr, tc, dr, dc, size)if (size = 1) return;t tile+ ; / L型骨牌号s size/2; / 分割棋盘/ 覆盖左上角子棋盘if (dr tr + s & dc tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s);else / 此棋盘中无特殊方格 boardtr + s - 1tc + s - 1 = t; / 用 t 号L型骨牌覆盖右下角 chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆盖其余方格 end if if (dr = tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盘中无特殊方格 boardtr + s - 1tc + s = t; / 用 t 号L型骨牌覆盖左下角 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆盖其余方格 end if （接下页）/ 覆盖左下角子棋盘 if (dr = tr + s & dc = tr + s & dc = tc + s) / 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s) else boardtr + stc + s = t / 用 t 号L型骨牌覆盖左上角 chessBoard(tr+s, tc+s, tr+s, tc+s, s) / 覆盖其余方格end if复杂度分析：T(n)=O(4k) 渐进意义下的最优算法了解下合并排序和快速排序：合并排序：基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。 复杂度分析T(n)=O(nlogn) 渐进意义下的最优算法快速排序：过程Split(Aleft: right,w)1. i left; x Aleft2. for j left+1 to right3. if Ajx then4. i i+15. if ij then 互换Ai和Aj6. end if7. end for 8.互换Aleft和Ai9.w i10.return A和w注意：1. 扩展汉诺塔问题：如果塔的个数变为a,b,c,d四个，现要将n个圆盘从a全部移动到d，移动规则不变，求移动步数最小的方案。2. 熟悉采用分治法求解大整数乘法基本过程。3. 通过棋盘覆盖问题理解算法的递归调用过程。4. 编写程序实现合并排序算法MergeSort和快速排序算法qSort。第三章动态规划基本思想是将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。基本步骤找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。1. 动态规划算法的基本要素：重叠子问题；最优子结构。2. 矩阵连乘问题(P47的例题)这里 的维数为 的位置只有 种可能设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n ： 当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,n当i0, wi0, vi 0, 1in, 要求找出一个n元向量(x1, x2, ., xn)，0xi1，1in ，使得 , 且 最大。用贪心算法解背包问题的基本步骤： 计算每种物品单位重量的价值vi/wi ;依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包;若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包;依此策略一直地进行下去，直到背包装满。3. 哈夫曼编码哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。 （哈夫曼提出了构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。 哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。 给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。 ）4. 最小生成树Prim算法 例如，对于右图中的带权图，按Prim算法选取边的过程如下图。输入：含权连通无向图G=(V,E)，V=1,2,n。输出：由G生成的最小耗费生成树T组成的边的集合。T ; S 1; R V-1 /初始化For i 2 to n if i邻接于1 then closesti 1 lowcosti c1i else lowcosti end ifEnd forFor k 1 to n-1 /寻找另外的n-1条边 令jR, 使得lowcostj最小 T T(j, closestj) /将边(j, closestj)加入T S S j /将顶点j加入S R R - j /从R中删除顶点j for 每个邻接于j的顶点wR if cjwlowcostw then closestw j lowcostw cjw end if end forEnd for 时间复杂度：O(n2)Kruskal算法例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如下图所示。输入：含权连通无向图G=(V,E)，V=1,2,n。输出：由G生成的最小耗费生成树T组成的边的集合。按非降序权重将E中的边排序For 每条边wR MAKESET(w) /将每条边作为一个单一集合End forT /初始化While |T|n-1 令(x, y)为E中的下一条边 if FIND(x)FIND(y) then 将(x, y)加入T UNION(x, y) end ifEnd while 时间复杂度：O(mlogm) 其中m=|E|第5章 回溯法回溯法和分支限界法的区别用回溯法基本框架解题、写算法。画图回溯法是在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。回溯法的基本做法是搜索用回溯法解题的算法框架（1）递归回溯（2）迭代回溯（3） 子集树算法框架（4）排列树算法框架分支限界法与回溯法（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。n后问题第六章常见的两种分支限界法（1）队列式(FIFO)分支限界法按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。（2）优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。子集树与排列树的区别。排列树：当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。子集树：当所给问题是从n个元素的集合s中找出满足某种性质的子集时，相应的解空间树称为子集树。1.分支界限法和回溯法主要区别在于求解目标和搜索方式不同。依据求解目标的不同，分支界限法和回溯法分别用广度优先遍历或者最小耗费优先、深度优先的方式搜索解空间树。2. 算法必须满足的四个特征是输入、输出、确定性、有限性。3. 问题的解空间树常见的有子集树、排列树两种类型。4. 动态规划算法求解问题的步骤？答：动态规划法适用于解最优化问题。通常可以按以下4个步骤设计：（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值；（3）以自底向上的方式计算最优值；（4）根据计算最优值时得到的信息构造最优解。5.利用回溯法解决问题包含哪些步骤？答：利用回溯法解题常包含以下3步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3） 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。6. 边界条件与递归方程是递归函数的二个要素7.分治法与动态规划法的不同点1、适合于用动态规划法求解的问题，分解得到的各子问题往往不是相互独立的；而分治法中子问题相互独立。2、动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问题时不必重新求解，而只需查询答案，故可获得多项式级时间复杂度，效率较高；而分治法中对于每次出现的子问题均求解，导致同样的子问题被反复求解，故产生指数增长的时间复杂度，效率较低。8.分支限界法与回溯法的相同点相同点：二者都是一种在问题的解空间树上搜索问题解的算法。不同点：1.在一