算法设计与分析课后习题

《算法设计与分析课后习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章1.算法分析题算法分析题1－1求下列函数的渐进表达式(1).3n^2+10n<3n^2+10n^2=13n^2=O(n^2)(2).n^2/10+2^n当n>5是，n^2<2^n所以，当n>=1时，n^2/10<2^n故:n^2/10+2^n<2^n+2^n=2*2^n=O(2^n)(3).21+1/n<21+1=22=O(1)(4).log(n^3)=3log(n)=O(log(n))(5).10log(3^n)=(10log3)n=O(n)算法分析题1-6(1)因为：f(n)=log(n^2)=2log(n);g(n)=log(n)+5所以：f(n)=Θ(log(n)+

2、5)=Θ(g(n))(2)因为：log(n)<√n;f(n)=2log(n);g(n)=√n所以：f(n)=O(g(n))(3)因为：log(n)n^2所

3、以:f(n)=Ω(g(n))(8)因为：f(n)=2^n;g(n)=3^n;2^n<3^n所以:f(n)=O(g(n))习题1－9证明：如果一个算法在平均情况下的计算时间复杂性为Θ(f(n)),该算法在最坏情况下所需的计算时间为Ω(f(n)).分析与解答：因此，Tmax(N)=Ω(Tavg(N))=Ω(Θ(f(n)))=Ω(f(n)).第二章算法分析题2-3设a[0:n-1]是已经排好序的数组。请改写二分搜索算法，似的当搜索元素x在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x的位置。分许与解答：改写二分搜索算法如下：typ

4、edefintTYPE_t;/**Functionname:BinarySearch*Parameters:*iIndex代表i的位置，即最大元素位置;*jIndex代表j的位置，即最小元素位置;*aArr[]:代表数组a[],且有序*xVar:代表元素x;*aLen:代表数组元素个数;*Returnvalue:*0:执行成功，最大元素位置和最小元素位置不等*1:执行成功，最大元素位置和最小元素位置相等*/staticintBinarySearch(TYPE_taArr[],intnLen,TYPE_txVar,int*iIndex,int*jIndex){intleft=0;i

5、ntright=nLen-1;intmiddle=(left+right)/2;while(left<=right){if(xVar==aArr[middle]){*iIndex=*jIndex=middle;return1;}if(xVar>aArr[middle]){left=middle+1;}else{right=middle-1;}middle=(left+right)/2;}*iIndex=right;*jIndex=left;return0;}算法分析题2–6对任何非零偶数n，总可以找到奇数m和正整数k，使得n=m*2^k.为了求出2个n阶矩阵的乘积，可以把一个n阶

6、矩阵划分成m×m个子矩阵，每个子矩阵2^k×2^k个元素。当需要求2^k×2^k的子矩阵的积时，使用Strassen算法。设计一个传统方法与Strasssen算法相结合的矩阵相乘算法，对于任何偶数n，都可以求出2个n阶矩阵的乘积。并分析算法的计算时间复杂度。分析与解答：将n阶矩阵分块为m×m的矩阵。用传统方法求2个m阶矩阵的乘积需要计算O(m^3)次2个2^k×2^k矩阵的乘积。用Strassen矩阵乘法计算2个2^k×2^k的矩阵的乘积需要的计算时间为O(7^k),因此算法的计算时间为O(7^k*m^3).算法分析题2-9设T[0,n-1]是n个元素的数组。对任一元素x，设S(

7、x)={i

8、T[i]=x}.当

9、S(x)

10、>n/2时，称x为T的主元素。设计一个线性时间算法，确定T[0:n-1]是否有一个主元素。分析与解答：如果T有一个主元素x，则x是T的中位数。反之，如果T的中位数不是T的主元素，则T没有主元素。下面算法设计为在一个线性时间中找中位数：typedefintT;#defineYES_MIDDLE_ELEMENT1#defineNO_MIDDLE_ELEMENT0/**Functionname:*IsExistMiddleElement*Par