计算机算法分析与设计

《计算机算法分析与设计》由会员分享，可在线阅读，更多相关《计算机算法分析与设计（15页珍藏版）》请在金锄头文库上搜索。

1、算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入：有外部提供的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。1.阶乘函数 阶乘函数可递归地定义为：边界条件递归方程边界条件与

2、递归方程是递归函数的二个要素2.Fibonacci 数列无穷数列 1，1，2，3，5，8，13，21，34，55，称为 Fibonacci 数列。它可以递归地定义为：当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。Ackerman 函数 A(n，m)定义如下：Ackerman 函数A(n，m) 的自变量 m 的每一个值都定义了一个单变量函数：M=0 时，A(n,0)=n+2M=1 时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2 ，和 A(1,1)=2 故 A(n,1)=2*nM=2 时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和 A

3、(1,2)=A(A(0,2),1)=A(1,1)=2，故 A(n,2)= 2n 。M=3 时，类似的可以推出M=4 时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。定义单变量的 Ackerman 函数 A(n)为，A(n)=A(n，n) 。定义其拟逆函数 (n)为： (n)=minkA(k)n 。即 (n) 是使 nA(k) 成立的最小的 k 值。(n)在复杂度分析中常遇到。对于通常所见到的正整数 n，有 (n) 4。但在理论上 (n)没有上界，随着n 的增加，它以难以想象的慢速度趋向正无穷大。6 排列问题设计一个递归算法生成 n 个元素r1,r2,rn的全排列。设

4、R=r1,r2,rn是要进行排列的 n 个元素，Ri=R-ri。集合 X 中元素的全排列记为 perm(X)。(ri)perm(X)表示在全排列 perm(X)的每一个排列前加上前缀得到的排列。R 的全排列可归纳定义如下： 当n=1 时，perm(R)=(r)，其中 r 是集合 R 中唯一的元素；当 n1 时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)构成。 7 整数划分问题0)!(!nn10)2()()nFnF1,20),1(),(20,),(mnnA在本例中，如果设 p(n)为正整数 n 的划分数，则难以找到递归关系，因此考虑增加一个自变量

5、：将最大加数 n1 不大于 m 的划分个数记作 q(n,m)。可以建立 q(n,m)的如下递归关系。(3) q(n,n)=1+q(n,n-1);正整数 n 的划分由 n1=n 的划分和 n1n-1 的划分组成。(4) q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整数 n 的最大加数 n1 不大于 m 的划分由 n1=m 的划分和n1n-1 的划分组成。8.Hanoi 塔问题 设 a,b,c 是 3 个塔座。开始时，在塔座 a 上有一叠共 n 个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为 1,2,n,现要求将塔座 a 上的这一叠圆盘移到塔座 b 上，并仍按同

6、样顺序叠置。在移动圆盘时应遵守以下移动规则：规则 1：每次只能移动 1 个圆盘；规则 2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则 3：在满足移动规则 1 和 2 的前提下，可将圆盘移至 a,b,c 中任一塔座上。public static void hanoi(int n, int a, int b, int c) if (n 0) hanoi(n-1, a, c, b);move(a,b);hanoi(n-1, c, b, a); 递归小结:优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无

7、论是耗费的计算时间还是占用的存储空间都比非递归算法要多。分治法的适用条件分治法所能解决的问题一般具有以下几个特征：1.该问题的规模缩小到一定的程度就可以容易地解决；2.该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质3.利用该问题分解出的子问题的解可以合并为该问题的解；4.该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题

8、分成大小相等的 k 个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。9 二分搜索技术给定已按升序排好序的 n 个元素 a0:n-1，现要在这 n 个元素中找出一特定元素 x。二分搜索算法：public static int binarySearch(int a, int x, int n) / 在 a0 amiddle) left = middle + 1;else right = middle - 1; return -1; / 未找到 x 算法复杂度分析：每执行一次算法的 while 循环

9、， 待搜索数组的大小减少一半。因此，在最坏情况下，while 循环被执行了O(logn) 次。循环体内运算需要 O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为 O(logn) 。合并排序：基本思想：将待排序元素分成大小大致相同的 2 个子集合，分别对 2 个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。 最坏时间复杂度：O(nlogn) 平均时间复杂度：O(nlogn) 辅助空间：O(n)快速排序:最坏时间复杂度： O(n2) 平均时间复杂度：O(nlogn) 辅助空间：O(n)或 O(logn)动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质1利

10、用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。2.递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。 备忘录方法备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时

11、查看，避免了相同子问题的重复求解。动态规划基本步骤:1.找出最优解的性质，并刻划其结构特征。2.递归地定义最优值。 3.以自底向上的方式计算出最优值。4.根据计算最优值时得到的信息，构造最优解。动态规划基本思想是将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。0/1 背包问题 0/1 背包问题的求解过程一、动态规划函数：物体 被装入背包的情况， 。约束方程和目标函数： 解向i

12、xi 1,0ix Mxwini1 inixpopt1ma量 。背包的载重量： ),(21nxX m：前 个物体中，能装入载重量为 的背包中的物体的最大价值， 。)joptii j j,2动态规划函数： （6.6.1）)(0(0joptti（6.6.2） iiiiiii wjpwjoptjt )(),(ax11二、求解过程 1、决策阶段：第一阶段，只装入一个物体，确定在各种不同载重量的背包下，能够得到的最大价值；第二阶段，装入前两个物体，确定在各种不同载重量的背包下，能够得到的最大价值；依此类推，直到第个阶段。n最后， 便是在载重量为 的背包下，装入 个物体时，能够取得的最大价值。)(moptn

13、mn2、解向量的确定从 的值向前倒推。t递推关系式：若 则 （6.6.3）)()(1joptjtii0ix若 则 ， （6.6.4）jti1i iwj例 6.6 有 5 个物体，其重量分别为 2,2,6,5,4，价值分别为 6,3,5,4,6，背包的载重量为 10，求装入背包的物体及其总价值计算结果，如图 6.7 所示。 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 6 6 6 6 6 6 6 6 6 2 0 0 6 6 9 9 9 9 9 9 9 3 0 0 6 6 9 9 9 9 1 1 14 4 0 0 6 6 9 9 9 10

14、 1 13 14 5 0 0 6 6 9 9 12 12 15 15 15 图 6.7 5 个物体的 0/1 背包问题的例子装入背包的物体为 。1,x0-1 背包问题给定 n 种物品和一背包。物品 i 的重量是 wi，其价值为 vi，背包的容量为 C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?0-1 背包问题是一个特殊的整数规划问题。设所给 0-1 背包问题的子问题的最优值为 m(i，j)，即 m(i， j)是背包容量为 j，可选择物品为 i，i+1，n 时 0-1 背包问题的最优值。由 0-1 背包问题的最优子结构性质，可以建立计算 m(i，j)的递归式如下。算法复杂度分析

15、：从 m(i，j) 的递归式容易看出，算法需要 O(nc)计算时间。当背包容量 c 很大时，算法需要的计算时间较多。例如，当 c2n 时，算法需要 (n2n)计算时间。 二叉搜索树（1）若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；niixv1manixCwini1,0nikkxvakixjxknik,10iii wjjimvwjijim0),1(,a),( nnjvj0),(（2）若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；（3 它的左、右子树也分别为二叉排序树最优二叉搜索树最优二叉搜索树 Tij 的平均路长为 pij，则所求的最优值为 p1,n。由最优二叉搜索树问题的最优子结构性质可建立计算 pij 的递归式如下记 wi,jpi,j 为 m(i,j)，则 m(1,n)=w1,np1,n=p1,n 为所求的最优值。计算 m(i,j)的递归式为注意到 可以得到 O(n2)的算法多段图的最短路径问题定义 6.1 有向连通赋权图 ，顶点集合 划分成 个不相交的子集 ， ， ，使得),(WEVGVkiVki12中的任一边 ，必有 ， ， 。称为多段图。E),(vuiumiv1令 ，称 为源点， 为收点。