《计算机算法基础》课后答案

计算机算法分析 习题课 第四章： 2 、 3、 5、 6、 10、 11、 23 下列情况下求解 (n)= ()2(/2) () 足够小否则 当 g(n)=O(1)和 f(n)=O(n)； g(n)=O(1)和 f(n)=O(1)。 设 n=2 T(n)=T(2k)=2T(2f(2k) =2(2 T(2f(2 +f(2k) =22T(221f(2 f(2k) = =2)+2)+22)+ +20f(2k) =2kg(n)+ 2)+22)+ +20f(2k) g(n)=O(1)和 f(n)=O(n) 当 g(n)=O(1)和 f(n)=O(n)时 不妨设 g(n)=a， f(n)=： T(n)=T(2k) = 22b+22b+ +20*22ka+an+(g(n)=O(1)和 f(n)=O(1) 当 g(n)=O(1)和 f(n)=O(1)时， 不妨设 g(n)=c， f(n)=d，则： T(n)=T(2k) = +20d =d(2=(c+d) (n) 根据 一个二分检索的递归过程 。 , x, j) if (2 if x=A(j if xA(, , x, j); if xA( :; j 0 例运行 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 361 时间复杂度 成功 : O(1),O(n),O(n) 最好，平均，最坏 失败 : O(n),O(n),O(n) 最好，平均，最坏 于含有 明 E=I+2n 其中， E， 证明：数学归纳法 当 n=1时，易知 E=2， I=0，所以 E=I+2 假设 n k(k0)时， E=I+2 此时新树内部结点为 满足： k+2k（ 1） 考察原树的外部路径长度和内部路径长度： = (h+1) （ 2） =Ik+h（ 3） 综合（ 1）（ 2）（ 3）式： = k+h+2 = k+h+2 = +2(k+1) 故命题成立。 程 (它的最好情况时间是什么？能说归并分类的时间是 (？ 最好情况： 对有序文件进行排序 分析 归并的次数不会发生变化 n)次 归并中比较的次数会发生变化（两个长 n/2序列归并） 最坏情况 两个序列交错大小 需要比较 最好情况 一个序列完全大于 /小于另一个序列 比较 n/2次 差异都是线性的，不改变复杂性的阶 最好情况也是 n), 平均复杂度 n)。 写一个 “由底向上 ”的归并分类算法，从而取消对栈空间的利用。 见数据结构 238 算法 R， n， 1X） 初始化 i 1 合并相邻的两个长度为 i n 2* 1 R， i， i l， i 2* X） . i i 2* 处理余留的长度小于 2* IF i+ 0，要用的处理时间 ，限期 解：根据 (30,20,18,6,5,3,1)，对应的期限为 (2,4,3,1,3,1,2)，按照算法 )=7(2), )=7(2), J(2)=3(4)； )=7(2), J(2)=4(3),J(3)=3(4)； )=6(1), J(2)=7(2),J(3)=4(3),J(4)=3(4)； 证明即使作业有不同的处理时间定理 里，假定作业 ，要用的处理时间 ，限期 定理 个作业的集合 , = 它使得 当且仅当 的次序又不违反任何一个期限的情况下来处理 . 证明：显然即使 （ 如果 J 中的作业可以按照 的次序而又不违反任何一个期限来处理，即对 次序中的任一个作业 k，应满足 = J 就是一个可行解。下面证明如果 J 是可行解， =得 J 中的作业可以按照 列排列而又不违反任何一个期限。 J 是可行解，则必存在 =使得对任意的 有 =们设 是按照 列的作业序列。假设 ，那么令 a 是使 最小下标，设 rb=然 ba，在 中将 交换，因为 然 以按期完成作业， 我们还要证明 间的作业也能按期完成 。因为 显然二者之间的所有作业 有 由于 是可行解，所以 1 ，所以作业 换后，仍满足 1 ，即所有作业可依新产生的排列 =次序处理而不违反任何一个期限，连续使用这种方法， 就可转换成 且不违反任何一个期限，定理得证。 对于 且仅当子集合 果 还没分配处理时间，则将它分配在时间片 a处理，其中 r r，且时间片 a是空的。 仿照例 习题 提供的数据集上执行算法 易证如果 然 如果 据定理 到 ik并且按照这个顺序，可以处理 对这一序列中的任意作业 果它的时间期限是 时间片 空的，则分配之；若时间片 空，则向前找最大的非空 r时间片， 1 r 是可行解，所以一定可以找到如此时间片。故命题得证。 n=7 (, =(3,5,20,18,1,6,30) (,(1,3,4,3,2,1,2) (=(30,20,18,6,5,3,1)， 对应的期限为 (2,4,3,1,3,1,2) b=n,d(i) =,4 =4 证明如果一棵树的所有内部节点的度都为 k，则外部节点数 1. 证明对于满足 n 1的正整数 n，存在一棵具有 (在一棵 个节点的度至多为 k)。进而证明 k. 证明：设某棵树内部节点的个数是 i，外部结点的个数是 n，边的条数是 e，则有 e=i+ik=e ik=i+ (i= n 1 证明如果 n 1，则在定理 q1,生成一棵最优的 (当（ q1, =（ 3,7,8,9,15,16,18,20,23,25,28）时，画出使用这一规则所得到的最优 3元归并树。 通过数学归纳法证明： 对于 n=1，返回一棵没有内部结点的树且这棵树显然是最优的。 假定该算法对于（ q1,，其中 m=(s+1 (s 0)，都生成一棵最优树， 则只需证明对于 (q1,，其中 n=(s+1)+1，也能生成最优树即可。 不失一般性，假定 q1,算法所找到的 是 q1,生成子树 T，设 T是一棵对于（ q1,的最优 果 P的 q1,则可以用q1, 样不增加 T的带权外部路径长度。 因此 是在 T中如果用其权为q1+一个外部结点来代换 T，则所生成的树 T是关于(T,的一棵最优归并树。由归纳假设，在使用其权为q1+那个外部结点代换了 程 T,的最优归并树。因此 q1,的最优归并树。 计算机算法分析 习题课 第六章 1 2 3 4 5 6 8 13 17 动态规划 优性原理 递推关系式（ 右图成立吗？为什么？ 递推关系式（ 什么对于含有负长度环的图不能成立？ 解： 成立，不包含负长度环 可以使节点间的长度任意小。 修改过程 其输出每对结点（ i,j）间的最短路径，这个新算法的时间和空间复杂度是多少？ 回忆算法： 法 131 算法 127 算法 D(i,j)/D(j) :从节点 最优路径中 算法 j)的同时也计算了 D(j) 3 7行 计算出 D( j ) 之后，即可计算最短路径。 9 11行 法 对矩阵进行初始化，每个元素赋值为边的长 度（如果没边则赋值成 1 5行 迭代计算最短路径长度 6 12行 仿照 每次计算最短路径的时候计算出 D(j) 再通过 D(j) 就可以表示出最短路径 k 1 to n 1 to n do j 1 to n do (i,j)A(i,k)+A(k,j) (i,j) A(i,k)+A(k,j) i,j) i,k) i 1 to n 输出最优路径 j 1 to n do of i to j i ) k i, j) k 0 do k) k k, j) 析 时间复杂度 第一个循环： O(第一个循环： O(第一个循环： O(空间复杂度 n,n) A(n,n) n,n) O(对于标识符集（ a1,a2,a3,=（ 已知成功检索概率为 P(1)=1/20, P(2)=1/5, P(3)=1/10, P(4)=1/20，不成功检索概率为 Q(0)=1/5, Q(1)=1/10, Q(2)=1/5, Q(3)=1/20, Q(4)=1/20，用算法(i,j)， R(i, j)和 C(i, j)（ 0 i, j 4）。 法 P（ i） P(1)=1/20, P(2)=1/5, P(3)=1/10, P(4)=1/20 Q（ i） Q(0)=1/5, Q(1)=1/10, Q(2)=1/5, Q(3)=1/20, Q(4)=1/20 P（ i） P(1)=1, P(2)=4, P(3)=2, P(4)=1 Q（ i） Q(0)=4, Q(1)=2, Q(2)=4, Q(3)=1, Q(4)=1 证明算法 ( 在已知根 R(i, j)， 0 i 1121()()() 最优性原理并不总是对可以将其解看成是一系列决策结果的所有问题成立。找两个最优性原理不成立的例子，并说明对这两个问题最优性原理为什么不成立。 多段图问题：路径和改为路径乘积并允许出现负数 计算机算法分析 习题课 第八章： 1、 3、 8、 9 改算法 它们只求出问题的一个解而不是问题的全部解 算法 8.1 n) n; : n) k 1 do (k)使得 X(k) T ( X(1), ,X(k k ( X(1), ,X(k) = X(1), ,X(k) ) 是一条抵达一答案节点的路径 X(1), ,X(k) k k 1 k 1 法 8.2 k) n, X(1:n) (k) X(k) T ( X(1), ,X(k k( X(1), ,X(k)= do X(1), ,X(k) 是一条抵达一答案结点的路径 X(1), ,X(k)