第2章习题
1. 证明当ak?0时，任何多项式p(n)?aknk?ak?1nk?1?...?a0属于集合?(nk)
aknk?ak?1nk?1?...?a0p(n)?ak>0 解：limk?limkn??nn??n
所以p(n)?aknk?ak?1nk?1?...?a0??(nk)
2. 对于下列每一种函数，指出它们属于哪一种?(g(n))类型（尽量使用最简单的g(n)），并给出证明。
a. (n2?1)10 b. 10n2?7n?3 c. 2nlg(n?2)2?(n?2)2lgd. 2n?1?3n?1 e. ?log2n?
118216n20?C20n?C20n?...?1(n2?1)10?lim?1 解： a. lim2020n??n??nnn2
所以 (n2?1)10??(n20)
10n2?7n?310n2?7n?3 b. lim?lim?1
n??n??nn2
所以
10n2?7n?3??(n)
nc. 由于2nlg(n?2)2??(nlgn)，(n?2)2lg??(n2lgn)。显然，当n??2
2时，nlgn>nlgn，所以2nlg(n?2)?(n?2)lg22n2??(n2lgn)
时，3>2，所
nnd. 由于2n?1??(2n)，3n?1??(lgn)。显然，当n??
以2n?1?3n?1??(3n)
e. log2n??log2n? 所以?log2n???(lgn) 3. 写出下列表达式的结果： a. ij b. ?1/i(i?1) c. ?i(i?1) ??ij?1?1i?1i?1nnnn?1a.解： ij??ij?1?1nn?i?1?nn(n?1)n(n?1)nn(n?1)n(n?1)n2(n?1)2 i????i?22i?1224b.解： i?1?1/i(i?1)??1?n11111111??...??1????...??1?22?3n(n?1)223nn?11n?n?1n?1n?1n?1c.解： i?1?i(i?1)?n?1i?1?i?2i?1?i?(n?1)n(2n?1)n(n?1)(n?1)n(n?1) ??623 4. 计算增长次数（即写出下列和的?(g(n))） a. ?(ii?0n?12?1) b ?lgii?2nn?12 c ?(i?1)2i?2ni?1 d ??(i?j) i?0j?0n?1i?1解：a. ?(n) b. ???1??(n3) 3i?0j?i?1k?in?2n?1 c. ?(n?2) n d. (?n) 3 5. x1,...,xn的采样方差n可以这样计算： ?xi?i?1n?x?2n?1或者 ，其中x??xi?1nin ?n?2?x?x?i??i??ni?1?i?1? n?1根据每个公式，对求方差时需要用到的除法、乘法和加/减运算的次数进行计算和比较。 解：第一个公式： 除法：2次， 乘法：n次， 加/减法：3n-1次 第二个公式：除法：2次， 乘法：n+1次， 加/减法：2n次 6. 考虑下面的算法 n2算法 secret(A[0..n-1]) //输入：包含n个实数的数组A minval ? A[0]; maxval ? A[0] for i ? 0 to n-1 do if A[i] < minval minval ? A[i] if A[j] > maxval maxval ? A[i] return maxval-minval 对于本算法，试回答下述问题： 1）该算法求的是什么？ 2）它的基本操作是什么？ 3）该基本操作执行了多少次？ 4）该算法的效率类型是什么？ 5）对该算法进行改进，若不可能，试证明之。 解：1）数组中最大的元素与最小元素之差 2）比较大小 3）2n次 4) ?(n) 5) 可以使用 if A[i] < minval minval ? A[i] else if A[j] > maxval maxval ? A[i] 替换 if A[i] < minval minval ? A[i] if A[j] > maxval maxval ? A[i] 在输入并非最糟糕的情况下，能在一定程度上提升算法的效率。 7. 已知算法GE如下： 算法GE(A[0..n-1, 0..n]) // 输入: 一个n行n+1列的实数矩阵A for i ?0 to n-2 do for j ? i+1 to n-1 do for k ? i to n do A[j,k] ? A[j,k] – A[i,k] * A[j,i]/A[i,i] 试问： 1）该算法的时间效率类型 2）该算法有何性能缺陷，试改进之。 解：1）将循环最内层的A[j,k] ? A[j,k] – A[i,k] * A[j,i]/A[i,i]中的乘法M（n） 或除法D(n)作为基本操作 53k?1M(n)=D(n) = ? 22故该算法的时间效率类型为?(n3) 2）由于在最内层循环A[j,k] ? A[j,k] – A[i,k] * A[j,i]/A[i,i]中， A[j,i]/A[i,i]并不包含最内层循环变量k。所以我们可以使用temp= A[j,i]/A[i,i], A[j,k] ? A[j,k] – A[i,k] * temp来减少除法的操作次数。 8. 求解下列递归关系 1） x(n)= 3x(n-1)，其中n>1，x(1)=4 2） x(n)= x(n/3)+ n，其中n>1，x(1)=1（给出n=3k的情况求解） 3） x(n)= 4x(n-1) + x(n-2) - 4，其中n>=0, x(0)=0, x(1)=1。 解：1）x(n) = 3x(n ? 1) = 3[3x(n ? 2)] = 3x(n ? 2) = 32[3x(n ? 3)] = 33x(n ? 3) = … = 3ix(n ? i) = ... = 3n?1x(1) = 4·3n?1. 2）x(n) = x(n/3) + n for n > 1, x(1) = 1 (solve for n = 2k) x(3k) = x(3k?1) + 3k = [x(3k?2) +3k?1] + 3k = x(3k?2) + 3k?1 +3k = [x(3k?3) + 3k?2] + 3k?1 + 3k = x(3k?3) + 3k?2 +3k?1 +3k = ... = x(3k?i) + 3k?i+1 +3k?i+2 + ... + 3k = ... = x(3k?k) + 31 + 32 + ... + 3k = 1 + 31 + 32 + ... +3k 3n?1= 23n?1= 22 3） 9. 试证明，对于一个任意十进制正整数n，下述算法BinRec(n)所做的加法运算的精确次数是?log2n?： 算法 BinRec(n) //输入：一个正的十进制整数n //输出：n的二进制表示的位数 if n=1 return 1 else return BinRec(?n/2?) + 1 解：由题知A(1)=0 当n=2k时； A(n) = A(2k) = A(2 k-1)+1 = A(2k-2)+2 ······ =A(2k-k)+k =A(1)+k 因为n=2k；所以k=log2n A(n) = log2n 10. 给定算法Min1(A[first..last])和Min2(A[first..last]) 算法1 Min1(A[first..last]) //输入last>= first且包含last-first+1个实数数组A if first= last return A[first]; else temp ? Min1(A[first..last-1]) if temp<= A[last] return temp else return A[last] 算法2 Min2(A[first..last]) //输入last>= first且包含last-first+1个实数数组A if first = last return A[first]; else temp1 ? Min2(A[first..??first?last?/2?] ) temp2 ? Min2(A[??first?last?/2?+1..last] ) if temp1 <= temp2 return temp1 else return temp2 试给出 1）算法1和算法2所做的基本操作次数的递推关系并求解。 2）算法1和算法2哪个更快。自已能否提出一个算法，使新算法效率胜过算法1和算法2。 解：1）1. 基本操作temp<= A[last]； M(n)=M(n-1)+1&M(1)=0 可知 M(n) = n； 2. 基本操作temp1<=temp2； M(n)=2*M(n/2)+1&M(1)=0可知 M(n)=n； 2) 一样快，求最小值比较方法就是线性方法。 除此之外，可以考虑位运算。 11. 试证明：