算法分析考试题.doc

给定数组a[0:n-1],试设计一个算法,在最坏情况下用n+[logn]-2次比较找出a[0:n-1] 中的元素的最大值和次大值. (算法分析与设计习题 2.16 ) （分治法） 算法思想 用分治法求最大值和次大值首先将问题划分，即将划分成长度相等的两个序列，递归求出左边的最大值次大值，再求出右边的的最大值次大值，比较左右两边，最后得出问题的解。 b、复杂度分析： 把问题划分为左右两种的情况，需要分别递归求解，时间复杂度可如下计算： 有递推公式为： T(n)=1 n=1 T(n)= 2T(n/2)+1 n1 所以，分治算法的时间复杂度是n+[logn]-2，当n为奇数时，logn取上线，当n为偶数时，logn取下线。//不知道为什么会-2！ C、代码实现： #include stdio.h int a[100]; void maxcmax(int i,int j,int max,int cmax) { int lmax,lcmax,rmax,rcmax; int mid; if (i==j) { max=a[i]; cmax=a[i]; } else if (i==j-1) if (a[i]a[j]) { max=a[j]; cmax=a[i]; } else { max=a[i]; cmax=a[j]; } else { mid=(i+j)/2; maxcmax(i,mid,lmax,lcmax); maxcmax(mid+1,j,rmax,rcmax); if(lmaxrmax) if(lcmaxrmax) { max=lmax; cmax=lcmax; } else { max=lmax; cmax=rmax; } else if(rcmaxlmax) { if(rmax==rcmax) { max=rmax; cmax=lmax; } else { max=rmax; cmax=rcmax; } } else { max=rmax; cmax=lmax; } } } int main() { int n; int max,cmax; printf(输入数组长度); scanf(%d,n); printf(输入数组:\n); for(int i=0;in;i++) {scanf(%d,a[i]);} maxcmax(0,n-1,max,cmax); printf(最大数为 %d\n,max); printf(次大数为 %d\n,cmax); return 0; } C、运行结果为 求数列的最大子段和(要求时间复杂为nlogn) (算法设计与分析 吕国英 清华大学出版社 135页 4..3.3 二分法变异) （分治法） （也可用动态规划算法 参看递归王晓东计算机算法设计与分析第三版p61页） a、基本思想： 用分治法求最大子段和首先将问题划分，即将一直序列划分成长度相等的两个序列， 这时会出现3种情况，即①最大子段和在第一个序列，②最大子段和在第二个序列和③ 最大子段和在第一个序列与第二个序列之间。然后，将3种情况的最大子段和合并，取三者之中的最大值为问题的解。 b、复杂度分析： 对应划分得到的情况①和②，需要分别递归求解，对应情况③，两个并列的for循环的时间 复杂度是O(n)，所以有递推公式为： T(n)=1 n=1 T(n)= 2T(n/2)+n-1 n1 所以，分治算法的时间复杂度是O(nlogn) c、代码实现 #includeiostream.h #define m 10 int MaxSubSum(int a[],int left,int right) { int sum=0; if(left==right) sum=a[left]0?a[left]:0; else { int i=(left+right)/2; int max1=MaxSubSum(a,left,i); int max2=MaxSubSum(a,i+1,right); int sum1=0,sum2=0; for(int j=i;j=left;j--) { sum1=sum1+a[j]; if(sum1sum2) sum2=sum1; }