1. T(n)?给定数组a[0:n-1],试设计一个算法,在最坏情况下用n+[logn]-2次比较找出a[0:n-1] 中的元素的最大值和次大值. (算法分析与设计习题 2.16 ) （分治法） a、 算法思想
用分治法求最大值和次大值首先将问题划分，即将划分成长度相等的两个序列，递归求出左边的最大值次大值，再求出右边的的最大值次大值，比较左右两边，最后得出问题的解。 b、复杂度分析：
把问题划分为左右两种的情况，需要分别递归求解，时间复杂度可如下计算： 有递推公式为：
T(n)=1 n=1 T(n)= 2T(n/2)+1 n>1
所以，分治算法的时间复杂度是n+[logn]-2，当n为奇数时，logn取上线，当n为偶数时，logn取下线。//不知道为什么会-2
！
C、代码实现： #include
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]rmax)
if(lcmax>rmax) { max=lmax; cmax=lcmax; } else { max=lmax; cmax=rmax; } else if(rcmax>lmax) { 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(\
printf(\输入数组:\\n\ for(int i=0;i return 0; } C、运行结果为 2. 求数列的最大子段和(要求时间复杂为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 n>1 所以，分治算法的时间复杂度是O(nlogn) c、代码实现 #include 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(sum1>sum2) sum2=sum1; } int sum3=0,sum4=0; for(j=i+1;j<=right;j++) { sum3=sum3+a[j]; if(sum3>sum4) sum4=sum3; } sum=sum2+sum4; if(sum void main() { int a[m],d; cout<<\请输入元素个数\ cin>>d; cout<<\请输入元素\ for(int i=0;i 运行结果为： 3. 设X[0：n-1] 和 Y[0：n-1]为两个数组，每个数组中含有n个已排好序的数。试设计一 个O(logn)时间算法，找出X和Y的2n个数的中位数。(分治法) a、基本思想： 解决问题的核心：找出将大问题分割成较小规模的相同问题的切割点，并递归定义大问题与子问题之间的关系。 确定切割点：对于两个数组，我们可以从他们中分别选取出一个中位数，称为x,y，并将两个数组的左右边界称之为aLeft,aRight,bLeft,bRight。对比两个中位数，如果X数组中的中位数大于Y数组中的中位数，且X数组中的元素个数为偶数个，则X数组被切割为X[aLeft,x-1]，Y被切割为Y[y,bRight]，如果X数组的元素个数不为偶数个的话，则直接将X切割为X[aLeft,x]。如果X数组的中位数小于Y数组的中位数，取值情况刚好相反。 递归关系：根据上面所述，对于原问题X[aLeft , aRight], Y[bLeft, bRight]。假设切割后的子问题为X[aLeft, x-1],Y[y,bRight]。则求解X[aLeft , aRight], Y[bLeft, bRight]问题的中位数，归结于求解子问题X[aLeft, x-1],Y[y,bRight]的中位数。 递归结束条件：当切割后得到的子问题的两个数组的长度都为1位时，整个递归结束。 b、复杂度分析： 因为数组比较的范围每次缩小一半，所以有递推公式为： T(n)=1 n=1 T(n)= T(n/2)+1 n>1 易算出时间复杂度为 O(logn) c、代码实现 #include int median(int x[],int y[],int xLeft,int xRight,int yLeft,int yRight){ if(xLeft==xRight) { return (x[xLeft]+y[yLeft])/2; } int xm=(xLeft+xRight)/2; int ym=(yLeft+yRight)/2; if((xLeft+xRight)%2==0)