算法设计与分析策略描述对于一个难以直接解决的大问题，如果该问题可以被分割成k个子问题（1<k≤n），而且这些子问题都可解，并且利用这些子问题的解可以求出原问题的解，那么我们就可以将原问题分割成一些规模较小的相同问题，从而各个击破，分而治之。分治法产生的子问题往往是原问题的较小模式，从而为使用递归技术提供了方便。通过反复使用分治手段，使子问题与原问题类型一致而规模不断缩小，最终使子问题缩小到容易求解的程度。提纲提纲基本概念什么是递归算法/函数？其他实例典型实例——阶乘函数典型实例——Fibonacci数列典型实例——Hanoi塔问题1Hanoi塔问题的递归算法Hanoi塔问题的复杂性分析算法复杂性同与运算能力的关系“世界末日问题”“世界末日”的推算基本概念分治法的基本思想divide-and-conquer(P){if(|P|<=n0)adhoc(P);dividePintosmallersubinstancesP1,P2,…,Pk;for(i=1,i<=k,i++)yi=divide-and-conquer(Pi);returnmerge(y1,y2,…,yk);}分治法的分割原则分治法的求解过程分治法的计算效率分析递归方程求解请参看“补充材料——分治递推关系的解.pdf”——从“…/算法分析/参考资料/”处下载提纲二分搜索技术大整数的乘法Strassen矩阵乘法棋盘覆盖合并排序快速排序线性时间选择最近点对问题循环赛日程表二分搜索技术二分搜索技术PublicstaticintbinarySearch(int[]a,intx,intn){//钊到x时返回其在数组中的位置，否则返回-1；intleft=0;intright=n-1;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle+1;elseright=middle-1;}return-1;//没找到}大整数的乘法大整数的乘法n/2位XY的乘积形式（1/2）☆所有加法和移位共用O(n)步运算☆设T(n)是2个n位整数相乘所需的运算总数XY的乘积形式（2/2）Strassen矩阵乘法Strassen矩阵乘法利用分治策略来求解矩阵乘法问题：与用原始定义直接计算相比，并没有降低计算复杂性解决方案结果分析：O(n2.81)<O(n3)Strassen矩阵乘法的计算时间复杂性比普通矩阵乘法有较大改进其他改进方案棋盘覆盖(a)棋盘覆盖举例存在的问题解决问题的出发点算法思想棋盘覆盖问题的算法复杂性分析合并排序合并排序的算法思想算法复杂性分析快速排序快速排序算法的基本思想快速排序算法的关键问题Privatestaticintpartition(intp,intr){inti=p;j=r+1;x=a[p];//将<x的元素交换到左边区域，将>x的元素交换到右边区域while(true){while(a[++i].compareTo(x)<0);//++i，直到找到>x的a[i]while(a[--j].compareTo(x)>0);//--i，直到找到<x的a[j]if(i>=j)break;MyMath.swap(a,i,j);//交换a[i]、a[j]的位置}a[p]=a[j];a[j]=x;returnj;}快速排序算法的复杂性分析快速排序算法在平均情况下的时间复杂性是O(nlogn)通常基于比较的排序算法的算法复杂度是O(n2)——快速排序算法因此得名基于随机选择策略的快速排序算法线性时间选择线性时间选择的基本思想PrivatestaticComparablerandomizedSelect(intp,intr,intk){if(p==r)returna[p];inti=randomizedpartition(p,r);intj=i-p+1;if(k<=j)returnrandomizedSelect(p,i,k);elsereturnrandomizedSelect(i+1,r,k-j);}对算法select的讨论说明寻找满足要求的划分基准x分析分析算法复杂性分析PrivatestaticComparableselect(intp,intr,intk){if(r-p)<5){bubbleSort(p,r);//对数组a[p:r]进行排序returna[p+k-1];}//将a[p+5*i,p+5*i+4]中的第3小元素与a[p+i]交换位置//找中