习题2-1求下列函数的渐进表达式：3n^2+10n;n^2/10+2n;21+1/n;logn^3;10log3^n。解答：3n^2+10n=O(n^2),n^2/10+2^n=O(2^n),21+1/n=O(1),logn^3=O(logn),10log3^n=O(n).习题2-3照渐进阶从低到高的顺序排列以下表达式：n!，4n^2,logn,3^n,20n,2,n^2/3。解答：照渐进阶从高到低的顺序为：n!、3^n、4n^2、20n、n^2/3、logn、2习题2-4(1)假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。在某台计算机上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？(2)若上述算法的计算时间改进为T(n)=n^2，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？(3)若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？解答：(1)设能解输入规模为n1的问题，则t=3*2^n=3*2^n/64,解得n1=n+6(2)n1^2=64n^2得到n1=8n(3)由于T（n)=常数，因此算法可解任意规模的问题。习题2-5XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为n，n^2，n^3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？解答：n'=100nn'^2=100n^2得到n'=10nn'^3=100n^3得到n'=4.64nn'!=100n!得到n'<n+log100=n+6.64习题2-6对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ（g(n)），并简述理由。解答：（1）f(n)=logn^2;g(n)=logn+5.logn^2=θ（logn+5）(2)f(n)=logn^2;g(n)=根号n.logn^2=O(根号n)(3)f(n)=n;g(n)=(logn)^2.n=Ω(（logn）^2)(4)f(n)=nlogn+n;g(n)=logn.nlogn+n=Ω（logn）(5)f(n)=10;g(n)=log10.10=θ(log10)(6)f(n)=(logn)^2;g(n)=logn.(logn)^2=Ω（logn）(7)f(n)=2^n;g(n)=100n^2.2^n=Ω（100n^2）(8)f(n)=2^n;g(n)=3^n.2^n=O(3^n)习题2-7证明：如果一个算法在平均情况下的计算时间复杂性为θ（f(n)），则该算法在最坏情况下所需的计算时间为Ω（f(n)）。证明：Tavg(N)=IeDn∑P(I)T(N,I)≤IeDn∑P(I)IeDnmaxT(N,I')=T(N,I*)IeDn∑P(I)=T(N,I*)=Tmax(N)因此，Tmax(N)=Ω（Tavg(N)）=Ω（θ(f(n))）=Ω（f(n)）习题2-8求解下列递归方程：So=0;Sn=2Sn-1+2^n-1.解答：1应用零化子化为齐次方程，2解此齐次方程的特征方程，3由特征根构造一般解，4再由初始条件确定待定系数，得到解为：Sn=(n-1)2^n+1习题2-9求解下列递归方程Ho=2;H1=8;Hn=4Hn-1-4Hn-2.解：Hn=2^(n+1)(n+1)第三章递归与分治策略习题3-1下面的7个算法都是解决二分搜索问题的算法。请判断这7个算法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给出算法的正确性证明。publicstaticintbinarySearch1(int[]a,intx,intn){intleft=0;intright=n-1;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle;elseright=middle;return-1;}publicstaticintbinarySearch2(int[]a,intx,intn){intleft=0;intright=n-1;while(left<right-1){intmiddle=(left+right)/2;if(x<a[middle])right=middle;elseleft=middle;}if(x==a[left])returnleft;elsereturn-1}publicstaticintbinarySearch3(int[]a,intx,intn){intleft=0;intright=n-1;while(left+1!=right){intmiddle=(left+right)/2;if(x>=a[middle])left=middle;elseright=middle;}if(x==a[left])returnleft;elsereturn-1;}publicstaticintbinarySearch4(int[]a,intx,intn){if(n>0x>=a[0]){intleft=0;intright=n-1;while(left<right){intmiddle=(left+right)/2;if(x<a[middle])right=middle-1;elseleft=middle;}if(x==a[left])returnleft;}return-1;}publicstaticintbinarySearch5(int[]a,intx,intn){if(n>0x>=a[0]){intleft=0;intright=n-1;while(left<right){intmiddle=(left+right+1)/2;if(x<a[middle])right=middle-1;elseleft=middle;}if(x==a[left])returnleft;}return-1;}publicstaticintbinarySearch6(int[]a,intx,intn){...