算法设计与分析-homework

1、一、已知下列递推式：C(n) = 1若n =1= 2C（n/2） + n 1 若n 2请由定理1 导出C(n)的非递归表达式并指出其渐进复杂性。定理1：设a,c为非负整数，b,d,x为非负常数，并对于某个非负整数k, 令n=ck, 则以下递推式f(n)=d若 n=1=af(n/c)+bnx若 n=2的解是f(n)= bnxlogcn + dnx若 a=cxf(n)= 若 acx解：取f(n) = C(n) 1,则 f(n) = 0 f(n) = 2C( n / 2) + n 2 若n=1 = 2f(n / 2) + n 若n= 2带入定理1：a = 2, d = 0, c = 2, b = 1

2、, x = 1,因为a=cx所以f(n) = nlog2n所以C(n) = f(n) + 1 = nlog2n + 1C(n)的渐进复杂度为O（nlog2n）二、由于Prim算法和Kruskal 算法设计思路的不同，导致了其对不同问题实例的效率对比关系的不同。请简要论述：1、如何将两种算法集成，以适应问题的不同实例输入；2、你如何评价这一集成的意义？解：Prime的时间复杂度为O(n2) （其中n 为顶点数）， Kruskal 算法的时间复杂度为 O(eln(e) （其中e为边数），因此对于顶点少的输入，适合Prime算法，对于边比较少的输入，适合Kruskal 算法。评价算法的优劣需要根据输

3、入数据的特点。对于不同特征的输入最适用的算法可能不同。三、分析以下生成排列算法的正确性和时间效率：HeapPermute(n)/实现生成排列的Heap算法/输入：一个正正整数n和一个全局数组A1.n/输出：A中元素的全排列if n = 1write Aelsefor i 1 to n doHeapPermute(n-1)if n is oddswap A1and Anelse swap Aiand An解：正确性：n=1时，输出A1n=2时，输出A1A2，A2A1n=3时，i=1时，HeapPermute(2)输出A1A2的全排列，并将A变为A2A1A3，并交换1,3位，得A3A1A2i=2时

4、，HeapPermute(2)输出A3A1的全排列，并将A变为A1A3A2，交换1,3位，得A2A3A1i=3时，HeapPermute(2)输出A2A3的全排列，并将A变为A3A2A1，交换1,3位，得A1A2A3算法运行结束后，A的元素顺序不变。n=4时，i=1时，HeapPermute(3)输出A1A2A3的全排列，并且A1A2A3顺序不变，交换1,4位，得A4A2A3A1i=2时，HeapPermute(3)输出A4A2A3的全排列，并且A4A2A3顺序不变，交换2,4位，得A4A1A3A2i=3时，HeapPermute(3)输出A4A1A3的全排列，并且A4A1A3顺序不变，交换3

5、,4位，得A4A1A2A3i=4时，HeapPermute(3)输出A4A1A2的全排列，并且A4A1A2顺序不变，交换4,4位，得A4A1A2A3算法运行结束后，数组A循环右移一位。因此可得出结论：当n为偶数时，HeapPermute(n)输出全排列后数组元素循环右移一位。当n为奇数时，HeapPermute(n)输出全排列后数组元素顺序保持不变。归纳法证明如下：(1)i=1时，显然成立。(2)i=k为偶数时，假设输出的是全排列，则i=k+1(奇数)时，k+1次循环中，每次前k个元素做全排列输出后循环右移一位，所以对换swap A1and An可以保证每次将前k个元素中的一个换到k+1的位置

6、，所以k+1次循环后输出的是A1k+1的全排列。(3)i=k为奇数时，假设输出的是全排列,则i=k+1(偶数)时，k+1次循环中，每次前k个元素做全排列输出后顺序保持不变，所以对换swap Aiand An可以保证每次将前k个元素中的一个换到k+1的位置，所以k+1次循环后输出的是A1k+1的全排列。正确性得证。时间复杂度：由算法流程得：F(n) = 1 n=1= n * (F(n - 1) + 2) n1= n * (n - 1) * (F(n - 2) + 2) + 2) = n(n - 1) * F(n-2) + 2n2= n! + 2 * nn-1因此时间复杂度为O(n!) + O(n

7、n-1)四、对于求n 个实数构成的数组中最小元素的位置问题，写出你设计的具有减治思想算法的伪代码，确定其时间效率，并与该问题的蛮力算法相比较。Min(A1.n, n, &loc)If(n = 1)Return A1Elseloc1, loc2Min1 = Min(A1.n/2, n/2, &loc1)Min2 = Min(An/2 + 1. n, n/2, &loc2)If(Min1 1= 2(2F(n/4) + 1) + 1 = 4F(n/4) + 2 + 1= 2kF(2k/2k) + 1 + 2 + + 2k-1 ( n=2k)= 2n 1复杂度为O（n），蛮力法也为O（n）五、请给出约瑟夫斯问题的非递推公式 J（n），并证明之。其中，n 为最初总人数，J(n) 为最后幸存者的最初编号。 解：非递推公式为：设J(n) = 2*b+1，其中n = 2m + b (0b1时，分两种情况讨论：当n=2k，即为偶数时，假设k = n/2时成立，即k = 2m + b，则J(k) = 2b+1，由n=2k得n = 2m+1 + 2bJ(n) = J(2k) = 2J(k) 1 = 2(2b+1) 1 = 4b + 1 = 2(2b) + 1，对n成立当n=2k+1，即为奇数时，假设k = (n-