习题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(xa[middle])left=middle;elseright=middle;return-1;}publicstaticintbinarySearch2(int[]a,intx,intn){intleft=0;intright=n-1;while(leftright-1){intmiddle=(left+right)/2;if(xa[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(n0&&x=a[0]){intleft=0;intright=n-1;while(leftright){intmiddle=(left+right)/2;if(xa[middle])right=middle-1;elseleft=middle;}if(x==a[left])returnleft;}return-1;}publicstaticintbinarySearch5(int[]a,intx,intn){if(n0&&x=a[0]){intleft=0;intright=n-1;while(leftright){intmiddle=(left+right+1)/2;if(xa[middle])right=middle-1;elseleft=middle;}if(x==a[left])returnleft;}return-1;}publicstaticintbinarySearch6(int[]a,intx,intn){if(n0&&x=a[0]){intleft=0;intright=n-1;while(leftright){intmiddle=(left+right+1)/2;if(xa[middle])right=middle–1;elseleft=middle+1;}if(x==a[left])returnleft;}return-1;}publicstaticintbinarySearch7(int[]a,intx,intn){if(n0&&x=a[0]){intleft=0;intright=n-1;while(leftright){intmiddle=(left+right+1)/2;if(xa[middle])right=middle;elseleft=middle;}if(x==a[left])returnleft;}return-1;}分析与解答:算法binarySearch1数组段左右游标left和right的调整不正确,导致陷入死循环。算法binarySearch2数组段左右游标left和right的调整不正确,导致当x=a[n-1]时返回错误。算法binarySearch3数组段左右游标left和right的调整不正确,导致当x=a[n-1]时返回错误。算法binarySearch4数组段左右游标left和right的调整不正确,导致陷入死循环。算法binarySearch5正确,且当数组中有重复元素时,返回满足条件的最右元素。算法binarySearch6数组段左右游标left和right的调整不正确,导致当x=a[n-1]时返回错误。算法binarySearch7数组段左右游标left和right的调整不正确,导致当x=a[n-1]时陷入死循环。习题3-2设a[0:n-1]是已排好序的数组。请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时,i和j相同,均为x在数组中的位置。分析与解答:改写二分搜索算法如下:publicstaticbooleanbinarySearch(int[]a,intx,intleft,intright,int[]ind){intmiddle;while(left=right){middle=(left+right)/2;if(x==a[middle]){ind[0]=ind[1]=middle;returntrue;}if(xa[middle])left=middle+1;elseright=middle-1;}ind[0]=right;ind[1]=left;returnfalse;}返回的ind[1]是小于x的最大元素位置,ind[0]是大于x的最小元素的位置。习题3-3设a[0:n-1]是有n个元素的数组,是非负整数。试设计一个算法讲子数组与换位。要求算法在最坏情况下耗时为,且只用到的辅助空间。分析与解答:算法:三次求反法Algorithmexchange(a,k,n);BeginInverse(n,0,k-1);inverse(n,k,n-1);inverse(n,0,n-1)End.Algorithminverse(a,i,j);Beginh=[(j-i+1)/2];Fork=0toh-1doBeginx=a[i+k];a[i+k]=a[j-k];a[j-k]=xend;end习题3-4如果在合并排序算法的分割步中,讲数组a[0;n-1]划分为[根号2】个子数组,每个子数组中有个元素。然后递归地对分割后的子数组进行排序,最后将所得到的个排好序的子数组合并成所要求的排好序的数组。设计一个实现上述策略的合并排序算法,并分析算法的计算复杂性。分析与解答:实现上述策略的合并排序算法如下:publicstaticvoidmergesort(int[]a,intleft,intright){if(leftright){intj=(int)Math.sqrt(right–left+1);if(j1){for(inti=0;ij;i++)mergesort(a,left+i*j,left+(i+1)*j-1);mergesort(a,left+i*j,right);}mergeall(a,left,right);}}其中,算法mergeall合并根号n个排好序的数组段。在最坏情况下,算法mergeall需要O(nlogn)时间。因此上述算法所需的计算时间T(n)满足:T(n)=O(1),n=1T(n)=根号n*T(根号n),n1T(n)=O(nlogn)此递归式的解为:。习题3-5设S1,S2...Sk是整数集合,其中每个集合中整数取值范围是,且,试设计一个算法,在时间内将分别排序。分析与解答:用桶排序或基数排序算法思想可以实现整数集合排序。习题3-6设X[0:n-1]和Y[0:n-1]为两个数组,每个数组中还有n个已排好序的数。试设计一个时间的算法,找出X和Y的2n个数的中位数。分析与解答:(1)算法设计思想考虑稍一般的问题:设X[i1:j1]和y[i2;j2]是X和Y的排序好的子数组,且长度相同,即j1-i1=j2-i2。找出这两个数组中2(i1-j1+1)个数的中位数。首先注意到,若X(i1)=Y(j2),则中位数median满足X(i)=median=Y(j2)。同理若X(i1)=Y(j2),则Y(j2)=median=X(i1)。设m1=(i1+j1)/2,m2=(i2+j2)/2,则m1+m2=i1+i2+(j1-i1)/2+(j2-i2)/2由于j1-i1=j2