《考研复习资料大汇总》由会员分享，可在线阅读，更多相关《考研复习资料大汇总（41页珍藏版）》请在金锄头文库上搜索。
1、分治法大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：O(n2) 效率太低 分治法:,X = Y = X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n + (ad+bc) 2n/2 + bd,a,b,c,d,复杂度分析 T(n)=O(n2) 没有改进,分治法大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：O(n2) 效率太低 分治法:,XY = ac 2n + (ad+bc) 2n/2 + bd 为了降低时间复杂度，必须减少乘法的次数。 XY = ac 2n + (a-b)(d-c)+ac+bd
2、) 2n/2 + bd XY = ac 2n + (a+b)(d+c)-ac-bd) 2n/2 + bd,复杂度分析 T(n)=O(nlog3) =O(n1.59)较大的改进,细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。,分治法循环赛日程表,设计一个满足以下要求的比赛日程表： (1)每个选手必须与其他n-1个选手各赛一次； (2)每个选手一天只能赛一次； (3)循环赛一共进行n-1天。,按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分
3、割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。,分治法线性时间选择,给定线性序集中n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素,template Type RandomizedSelect(Type a,int p,int r,int k) if (p=r) return ap; int i=RandomizedPartition(a,p,r), j=i-p+1; if (k=j) return RandomizedSelect(a,p,i,k); else return RandomizedSelect(a,i+1,r,k-j
4、); ,在最坏情况下，算法randomizedSelect需要O(n2)计算时间 但可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。,分治法线性时间选择,如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的倍(01是某个正常数)，那么就可以在最坏情况下用O(n)时间完成选择任务。,例如，若=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)T(9n/10)+O(n) 。由此可得T(n)=O(n)。,将n个输入元素划分成n/5
5、个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。 递归调用select来找出这n/5个元素的中位数。如果n/5是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。,分治法线性时间选择,设所有元素互不相同。在这种情况下，找出的基准x至少比3(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，而n/5个中位数中又有(n-5)/10个小于基准x。同理，基准x也至少比3(n-5)/10个元素小。而当n75时，3(n-5)/10n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。,Type S
6、elect(Type a, int p, int r, int k) if (r-p75) 用某个简单排序算法对数组ap:r排序; return ap+k-1; ; for ( int i = 0; i=(r-p-4)/5; i+ ) 将ap+5*i至ap+5*i+4的第3小元素 与ap+i交换位置; /找中位数的中位数，r-p-4即上面所说的n-5 Type x = Select(a, p, p+(r-p-4)/5, (r-p-4)/10); int i=Partition(a,p,r, x), j=i-p+1; if (k=j) return Select(a,p,i,k); else r
7、eturn Select(a,i+1,r,k-j); ,复杂度分析 T(n)=O(n),上述算法将每一组的大小定为5，并选取75作为是否作递归调用的分界点。这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20=n，01。这是使T(n)=O(n)的关键之处。当然，除了5和75之外，还有其他选择。,动态规划0-1背包问题,给定 n 种物品和一背包。物品 i 的重量是 wi，其价值为 vi，背包的容量为 C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 0-1背包问题是一个特殊的整数规划问题。,动态规划 0-1背包问题,设所给0-1背包问题的子问题,的最优值为m
8、(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。,考虑下列实例： n=3, 物品重量 (w1, w2, w3)=(2, 3, 4), 物品价值(p1, p2, p3)=(1, 2, 5), 背包容量C=6 解：,m(1, 6)=max m(2, 6), m(2, 6-2)+1 ,m(2, 6)=max m(3, 6), m(3, 6-3)+2 ,m(2, 4)=max m(3, 4), m(3, 4-3)+2 ,m(3, 6)=5 m(3, 3)=0,=5,=5,=6,解向量为
9、(x1, x2, x3)=(1, 0, 1),m(3, 4)=5 m(3, 1)=0,动态规划最长公共子序列,若给定序列X=x1, x2, , xm，则另一序列Z=z1, z2, , zk，是X的子序列是指存在一个严格递增下标序列i1, i2, , ik使得对于所有 j=1, 2, , k 有：zj = xij。 例如，序列Z=B, C, D, B是序列X=A, B, C, B, D, A, B的子序列，相应的递增下标序列为2, 3, 5, 7。 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 给定2个序列X=x1, x2, , xm和Y=y1,
10、 y2, , yn，找出X和Y的最长公共子序列。,动态规划最长公共子序列的结构,设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk ，则 (1)若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。 (2)若xmyn且zkxm，则Z是Xm-1和Y的最长公共子序列。 (3)若xmyn且zkyn，则Z是X和Yn-1的最长公共子序列。,由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。,子问题的递归结构,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。
11、用 cij 记录序列和的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当 i=0 或 j=0时，空序列是 Xi 和 Yj 的最长公共子序列。故此时cij=0。其它情况下，由最优子结构性质可建立递归关系如下：,计算最优值,由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。,void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i =cij-1) cij=ci-1j; bij=2; else cij
12、=cij-1; bij=3; ,构造最长公共子序列 void LCS(int i，int j，char *x，int *b) if (i = =0 | j= =0) return; if (bij= 1) LCS(i-1，j-1，x，b); coutxi; else if (bij= 2) LCS(i-1，j，x，b); else LCS(i，j-1，x，b); ,贪心法活动安排问题,活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用
13、公共资源。,贪心法活动安排问题,设有 n 个活动的集合 E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动 i 都有一个要求使用该资源的起始时间 si 和一个结束时间 fi ,且 si fi 。如果选择了活动 i，则它在半开时间区间si, fi)内占用资源。若区间 si, fi)与区间 sj, fj)不相交，则称活动 i 与活动 j 是相容的。也就是说，当sifj 或 sjfi 时，活动 i 与活动 j 相容。,在下面所给出的解活动安排问题的贪心算法 : int greedySelector(int s, int f, boolea
14、n a) int n=s.length; a1=true; int j=1; int count=1; for (int i=2; i=fj) ai=true; j=i; count+; else ai=false; return count; ,各活动的起始时间和结束时间存储于数组 s和 f 中且按结束时间的非减序排列,贪心法活动安排问题,由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便
15、安排尽可能多的相容活动。 算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。,贪心法活动安排问题,例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：,贪心法活动安排问题,4.1 活动安排问题,算法greedySelector 的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。,贪心法多机调度问题,多机调度问题要求给出一种作业调度方案，使所给的 n个作业在尽可能短的时间内由 m 台机器加工处理完成。 设有 n 个独立的作业1,2,n，由 m 台相同的机器进行加工处理。作业 i 所需的处理时间为 ti。 这个问题是 NP 完全问题，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。,约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。,贪心法多机调度问题,采用最长处理
