您现在的位置:主页 > 香港百合图库总站 >

EX5-20132022

来源:本站原创 发布时间:2021-10-24 点击数:

  第五章 部分习题解答 P99 【仅供参考】 5.8 当输入由下列区间中 n 个正整数组成时,以 n 为大小说明算法 RADIXSORT 的时间复杂性。 (a)[1……n] (b)[1..... n 2 ] (c)[1…. 2n ] 解:注意到 RADIXSORT 算法主要是对规模为正整 n 的数组,按低位到高位的 次序排序,每位排序的时间复杂度为(n),则若每个数的位数为 k。引用乘法原 理,其时间复杂度为(kn)。不失一般性,令 k=logn。 (a) n 的位数 k 为 log n,即需要 logn 张表来存储每一次排序的结果,而每一 次的代价为 (n),故总的时间代价为 (n log n)。 (b) 如上,对规模为 n2 的数组,因最大数为 n2,位数 k 为 log n2 = 2 log n,故 时间代价为 (2n log n) = (n log n)。 (c) 对规模为 2n 的数组,因最大数为 2n,位数 k 为 log 2n = n,故时间代价为 (n2)。 5.9 设 A[1……n] 是 在 区 间 [1…n!] 中 的 正 整 数 组 成 的 数 组 , 对 于 算 法 BOTTOMUPSORT 和算法 RADIXSORT,哪一种更快? 解:因为 A[1..n]中元素取值于区间[1.. n!], 首先研究 log n!来考虑位数。由于 n n!=n*(n-1)*(n-2)*····*1,log n!= log i = (n log n) 1 因此 k=O(nlog n),从而算法 RADIX 时间复杂度为 O(n2logn) 。 BOTTOMUPSORT 算法对于 n 规模的数组排序其时间复杂度为 (n log n)。 而 RADIXSORT 的时间复杂度取决于规模和最大位数,显然最大位数 k=log n!= (n log n), 因此其时间复杂度为 ( n 2 log n)。显然 BOTTOMUPSORT 的时间复杂度更低。由此我们 可以得到启示,当数组的规模不是太大而元素的位数很大时宜用 BOTTOMUPSORT 算法, 而规模大但位数少的则宜用 RADIXSORT 算法。 5.23 修 正 算 法 PERMUTATIONS2 , 使 数 1 , 2 ,····, n 的 排 列 按 算 法 PERMUTATIONS2 产生的倒序生成。 解 : 要 得 到 恰 如 PERMUTATIONS2 产 生 排 列 的 倒 序 排 列 , 只 需 在 算 法 PERMUTATIONS2 的 Procedure perm2 的步骤 3 中,将“for j←1 to n” 改成 “for j←n to 1 ” 即可。完整算法如下: 算法 Reverse-PERMUTATIONS2 输入:正整数 n。 输出:数 1,2,……,n 的所有可能排列。 1.for j←1 to n 2. P[j] ← 0 3. end for 4. perm2(n) 过程 perm2(m) 1. if m = 0 then output P[1…n] 2. else 3. for j←n to 1 // 这个题目同时注意在课堂上的关于 一个实例的演算过程,会增加认识的具体化。 4. if P[j]=0 then 5. P[j] ← n–m + 1 6. perm2(m-1) 7. P[j] ← 0 8. end if 9. end for 10. end if 可以对于这个算法,用 1,2,3 的简单实例,运算一下,就会更加明了。 5.31 对下面的说法,证明其为正确或错误:如果算法 MAJORITY 里过程 candidate 的第 7 步中 j=n 但 count=0,那么 c 是多数元素。 解:错误。例如:(1,3,5,4,8,6,2,7)c=2 count=0。 {分析如下: 首先,明确多数元素的概念,当 A[1……n]中有元素值为 c 的个数多于 int(n/2) 时,c 为多数元素。MAJORITY 算法的过程 candidate(m)采用了如下思想:在 原序列去除两个不同的元素后,那么在原序列中得多数元素在新序列中还是多数 元素。 这一思想若要真正实现多数元素的查找,必须是对确实有多数元素的数组操作才 有效。一肖中特平管家婆 因为,如果去除的两个相异元素可能是“一个多数元素,一个非多数元素”或“两 个非多数元素”,这样多数元素始终能保持多数的地位。但是在数组中如果本来 就没有多数元素的情况下,该操作只会成对的删去数组中的相异元素,最终 c 等 于数组的最后一个(n 为奇数)或倒数第二个元素(n 为偶数)。 对于过程化的分治算法 candidate(m),先假定 A[1]为多数元素,count 初值为 1, 以 j 为指针从 2 到 n 开始遍历数组,凡遇到多数元素 count 自增,凡遇与非多数 元素 count 自减,当 count 为 0 时表征已遍历的那段数组(必有偶数个)中任何 元素都不超过该段数组容量的一半,删去该段数组显然不影响多数元素在剩余数 组段中的多数地位。2~6 中的 while 循环正体现了这一操作。其终止条件为就 j=n 或 count=0;当 count=0 且 jn 时,剩余剩余数组尚不为空,所以要递归调用 candidate(j+1)以对剩余数组进行递归子规模的操作。 当 j=n 时,表征数组以遍历搜索完毕,此时若原数组中有多数元素,那么自然 count0 且 c=多数元素,但是如果原数组中并没有多数元素存在时,可能的情形 比较多。} 略举三例如下(3,5,8,7,4,4,4,4) c=4 count=4 或(1,3,5,4,8,6,2,7)c=2 count=0 或(1,2,3,4,5,6,7,8,9)c=9;count=1 显然在不存在多数元素的情况下算法 candidate(m)的第七步中 c 的值和 count 的值并没有多大的意义和规律,并不能用 c 作为多数元素输出。 解二: 错误。用反反例说明。当 n 为偶数,且只存在两种个数相同的元素时,此时该序 列应该不存在多数元素,但是执行到 candidate 第七步时,刚好是 j=n 且 count=0, 此时的 c 被当为了多数元素,因此该说法是错误的。 反例:取 n=4; A[1...4]=1,3,1,0; 此时,满足题目的要求,但返回的 c=1 不 是多数元素。 算法中,对最后返回的 c 还必须通过的与原数组中的元素一个一个比较并记录出 现的次数,才能判断并确定 c 是否为多数元素。 5.32 对下面的说法,证明其为正确或错误:如果算法 MAJORITY 里过程 candidate 的第 7 步中 j=n 并且 count0,那么 c 是多数元素。 解:错误。执行算法的过程中,我们“删除”了一些元素,最后我们得出的 c 只 能是候选元素,还要经一次序列扫描计数才能判断结果。 反例一:一个 1,2,3,3,的序列,不存在多数元素,但是我们刚开始在判断 1 是否 是多数元素时就把 1,2“删除”了,最后当 c=3 时,也有 j=n 且 count0,于是就 把 3 当为了多数元素,这样是不对的。 反例二:1,2,3,4,5,6,7,8,9; c=9;count=1。但 9 并非多数元。