第2章习题1. 证明当0>k a 时，任何多项式011...)(a n a n a n p k k k k +++=--属于集合)(k n Θ解：110...()lim lim k k k k k k k n n a n a n a p n a n n--→∞→∞+++==>0 所以011...)(a n a n a n p k k k k +++=--∈)(k n Θ2. 对于下列每一种函数，指出它们属于哪一种))((n g Θ类型（尽量使用最简单的g(n)），并给出证明。
a. 102)1(+nb. 37102++n nc. 2lg )2()2lg(222nn n n +++d. 1132-++n ne. ⎣⎦n 2log解： a. 2011821621020202020...1(1)lim lim 1n n n C n C n n n n→∞→∞+++++==所以 102)1(+n ∈20()n Θb. lim 1n n n →∞==所以37102++n n ∈()n Θc. 由于22lg(2)n n +∈(lg )n n Θ，2(2)lg 2nn +∈2(lg )n n Θ。
显然，当n →∞时，2lg n n >nlgn ，所以2lg)2()2lg(222nn n n +++∈2(lg )n n Θd. 由于12+n ∈(2)n Θ，13-n ∈(lg )n Θ。
显然，当n →∞时，3n>2n，所以1132-++n n ∈(3)n Θe. n 2log ≤⎣⎦n 2log <n 2log +1, 又n 2log ∈(lg )n Θ，n 2log +1∈(lg )n Θ所以⎣⎦n 2log ∈(lg )n Θ3. 写出下列表达式的结果：a.∑∑==n i n jij 11b. ∑=+n i i i 1)1(/1 c. ∑-=+11)1(n i i i a.解：4)1(2)1(2)1(2)1(2)1(221111+=+∙+=+=+=∑∑∑∑====n n n n n n i n n i n n ij n i ni n i njb.解：1111111...3121211)1(1...321211)1(/11+=+-=+-++-+-=+++⨯+⨯=+∑=n n n n n n n i i ni c.解：3)1()1(2)1(6)12()1()1(1111211+-=-+--=+=+∑∑∑-=-=-=n n n n n n n n i i i i n i n i n i4. 计算增长次数（即写出下列和的))((n g Θ） a.∑-=+12)1(n i ib∑-=122lg n i ic∑=-+ni i i 212)1( d∑∑-=-=+101)(n i i j j i解：a. 3()n Θ b. 21301 1()n n ni j i k in --==+==Θ∑∑∑c. (2)nn Θ∙d.3()n Θ5. n x x ,...,1的采样方差n 可以这样计算：()112--∑=n x x nii ，其中nxx ni i∑==1或者12112-⎪⎪⎭⎫ ⎝⎛-∑∑==n nx x n i i ni i根据每个公式，对求方差时需要用到的除法、乘法和加/减运算的次数进行计算和比较。
解：第一个公式： 除法：2次， 乘法：n 次， 加/减法：3n-1次 第二个公式：除法：2次， 乘法：n+1次， 加/减法：2n 次6. 考虑下面的算法算法secret(A[0..n-1])//输入：包含n个实数的数组Aminval ←A[0]; maxval ← A[0]for i ← 0 to n-1 doif A[i] < minvalminval ← A[i]if A[j] > maxvalmaxval ← A[i]return maxval-minval对于本算法，试回答下述问题：1）该算法求的是什么？2）它的基本操作是什么？3）该基本操作执行了多少次？4）该算法的效率类型是什么？5）对该算法进行改进，若不可能，试证明之。
解：1）数组中最大的元素与最小元素之差2）比较大小3）2n次4)()nΘ5)可以使用if A[i] < minvalminval ← A[i]else if A[j] > maxvalmaxval ← A[i]替换if A[i] < minvalminval ← A[i]if A[j] > maxvalmaxval ← A[i]在输入并非最糟糕的情况下，能在一定程度上提升算法的效率。
7.已知算法GE如下：算法GE(A[0..n-1, 0..n])// 输入: 一个n行n+1列的实数矩阵Afor i ←0 to n-2 dofor j ← i+1 to n-1 dofor k ← i to n doA[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)作为基本操作M(n)=D(n) =1 53 22k+ +故该算法的时间效率类型为3()nΘ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)=42）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)] = 32x(n −2)= 32[3x(n −3)] = 33x(n −3)= …= 3i x(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 + (3)=31 2 n-=31 2 n-3）9.试证明，对于一个任意十进制正整数n，下述算法BinRec(n)所做的加法运算的精确次数是[]n2log：算法BinRec(n)//输入：一个正的十进制整数n//输出：n 的二进制表示的位数 if n=1 return 1else return BinRec(⎣⎦2/n ) + 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=2log n A(n) = 2log n10. 给定算法Min1(A[st])和Min2(A[st])算法1 Min1(A[st])//输入last>= first 且包含last-first+1个实数数组Aif first= last return A[first];else temp ← Min1(A[st-1]) if temp<= A[last] return temp else return A[last]算法2 Min2(A[st])//输入last>= first 且包含last-first+1个实数数组Aif first = last return A[first];else temp1 ← Min2(A[first..()⎣⎦2/last first +] ) temp2 ← Min2(A[()⎣⎦2/last first ++st] )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. 试证明：当≥n1时，()nnFnFnFnF⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡+-111)1()()(1解：用数学归纳法证明：当n=1时，(0)(1)01(1)(2)12F FF F⎡⎤⎡⎤=⎢⎥⎢⎥⎣⎦⎣⎦成立；设当n=k时，(1)()01()(1)11kF k F kF k F k-⎡⎤⎡⎤=⎢⎥⎢⎥+⎣⎦⎣⎦成立；则当n=k+1时，()(1)()()(1)(1)(2)()(1)(1)()F k F k F k F k F kF k F k F k F k F k F k++-⎡⎤⎡⎤=⎢⎥⎢⎥+++-++⎣⎦⎣⎦1(1)()01010101**()(1)11111111k k F k F kF k F k+ -⎡⎤⎡⎤⎡⎤⎡⎤⎡⎤===⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥+⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦也就是说，当n=k+1时，成立，证毕。
12.考虑基于定义计算第n个Fibonacci数的递归算法F(n):算法F(n)//根据定义，递归计算第n个Fibonacci数//输入：一个非负整数n//输出：第n个Fibonacci数if n <= 1 return nelse return F(n-1) + F(n-2)令C(n)和Z(n)分别是F(n)调用F(1)和F(0)的次数，试证明：1）C(n) = F(n)2）Z(n) = F(n-1)解：用数学归纳法证明：当n=1时，C（n）= 1 = F（1），Z（n）= 0 = F（0）成立；n=2时，C（n）= 2 = F（2），Z（n）= 1 = F（1）成立；假设当n=k-1时，有C(k-1) = F(k-1)，Z(k-1) = F(k-2) 成立；当n=k时，有C(k) = F(k)，Z(k) = F(k-1) 成立；则当n=k+1时，F（k+1）= F（k）+ F（k-1），那么，C（k+1）= C（k）+ C（k-1）= F（k）+ F（k-1）= F（k+1）Z（k+1）= Z（k）+ Z（k-1）= F（k-1）+ F（k-2）= F（k）也就是说，当n=k+1时，成立，证毕。
