下载文档原格式
1、以下哪个算法的时间复杂度是O(1)？A. 冒泡排序的最坏情况B. 二分查找的最坏情况C. 在一个无序数组中线性查找特定元素D. 快速排序的平均情况（答案：B）2、对于一个大小为n的有序数组，使用二分查找算法查找一个元素的时间复杂度是？A. O(n)B. O(n2)C. O(log n)D. O(n!)（答案：C）3、以下哪个数据结构在最坏情况下的插入操作时间复杂度是O(1)？A. 链表B. 动态数组C. 平衡二叉搜索树D. 哈希表（假设冲突极少）（答案：D）4、归并排序的时间复杂度是？A. O(n)B. O(n log n)C. O(n2)D. O(2n)（答案：B）5、在一个有n个顶点的图中，使用邻接矩阵表示，检查是否存在从顶点i到顶点j的边的时间复杂度是？A. O(n)B. O(n2)C. O(1)D. O(log n)（答案：C）6、以下哪个算法的时间复杂度与问题规模n成指数关系？A. 迪杰斯特拉算法求最短路径B. 广度优先搜索C. 旅行商问题的暴力求解D. 堆排序（答案：C）7、在一个长度为n的链表中，删除指定元素的时间复杂度（假设链表未排序且元素位置未知）是？A. O(1)B. O(n)C. O(log n)D. O(n2)（答案：B）8、下列哪个算法的时间复杂度是O(n log n)，并且常用于排序？A. 插入排序B. 选择排序C. 堆排序D. 冒泡排序（答案：C）9、对于一个包含n个元素的集合，求其所有子集的时间复杂度是？A. O(n)B. O(n2)C. O(2n)D. O(n!)（答案：C）10、在一个二叉搜索树中，平均情况下查找一个元素的时间复杂度是？A. O(1)B. O(n)C. O(log n)D. O(n2)（答案：C）。
算法练习题---算法概述一、选择题1、下面关于算法的描述，正确的是（）A、一个算法只能有一个输入B、算法只能用框图来表示C、一个算法的执行步骤可以是无限的D、一个完整的算法，不管用什么方法来表示，都至少有一个输出结果2、一位爱好程序设计的同学，想通过程序设计解决“韩信点兵”的问题，他制定的如下工作过程中，更恰当的是（）A、设计算法，编写程序，提出问题，运行程序，得到答案B、分析问题，编写程序，设计算法，运行程序，得到答案C、分析问题，设计算法，编写程序，运行程序，得到答案D、设计算法，提出问题，编写程序，运行程序，得到答案3、下面说法正确的是（）A、算法+数据结构=程序B、算法就是程序C、数据结构就是程序D、算法包括数据结构4、衡量一个算法好坏的标准是（）。
A、运行速度快B、占用空间少C、时间复杂度低D、代码短5、解决一个问题通常有多种方法。
若说一个算法“有效”是指( )。
A、这个算法能在一定的时间和空间资源限制内将问题解决B、这个算法能在人的反应时间内将问题解决C、这个算法比其他已知算法都更快地将问题解决D、A和C6、算法分析中，记号O表示（），记号Ω表示（）。
A.渐进下界B.渐进上界C.非紧上界D.非紧下界7、以下关于渐进记号的性质是正确的有：（）A.f(n)(g(n)),g(n)(h(n))f(n)(h(n))=Θ=Θ⇒=ΘB.f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n))==⇒=C. O(f(n))+O(g(n)) = O(min{f(n),g(n)})D.f(n)O(g(n))g(n)O(f(n))=⇔=8、记号O的定义正确的是（）。
A. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤f(n) ≤cg(n) }；B. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤cg(n) ≤f(n) }；C. O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0有0 ≤f(n)<cg(n) }；D. O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0有：0 ≤cg(n) <f(n) }；9、记号Ω的定义正确的是（）。
算法设计与分析试卷一、填空题（20分，每空2分）1、算法的性质包括输入、输出、＿＿＿、有限性。
2、动态规划算法的基本思想就将待求问题＿＿＿＿＿、先求解子问题，然后从这些子问题的解得到原问题的解。
3、设计动态规划算法的4个步骤：（1）找出＿＿＿＿，并刻画其结构特征。
（2）＿＿＿＿＿＿＿。
（3）＿＿＿＿＿＿＿。
（4）根据计算最优值得到的信息，＿＿＿＿＿＿＿。
4、流水作业调度问题的johnson算法：（1）令N1=＿＿＿,N2={i|ai>=bj};（2）将N1中作业依ai的＿＿＿。
5、对于流水作业高度问题，必存在一个最优调度π，使得作业π（i）和π（i+1）满足Johnson不等式＿＿＿＿＿。
6、最优二叉搜索树即是＿＿＿的二叉搜索树。
二、综合题（50分）1、当（a1,a2,a3,a4,a5,a6）=(-2,11,-4,13,-5,-2)时，最大子段和为∑ak(2<=k<=4)＿＿＿＿（5分）2、由流水作业调度问题的最优子结构性质可知，T（N，0）=＿＿＿＿＿＿（5分）3、最大子段和问题的简单算法(10分)int maxsum(int n,int *a,int & bestj){intsum=0;for (int i=1;i<=n;i++)for (int j=i;j<=n;j++)int thissum=0;for(int k=i;k<=j;k++)＿＿＿＿＿;if(thissum>sum){sum=thissum;＿＿＿＿＿＿；bestj=j;}} return sum;}4、设计最优二叉搜索树问题的动态规划算法OptimalBinarysearchTree? (15分)Void OptimalBinarysearchTree(int a,int n,int * * m, int* * w){for(int i=0;i<=n;i++) {w[i+1][i]=a[i]; m[i+1][i]=＿＿＿＿;}for(int r=0;r<n;r++)for(int i=1;i<=n-r;i++){int j=i+r;w[i][j]=w[i][j-1]+a[j]+b[j];m[i][j]=＿＿＿＿＿＿;s[i][j]=i;for(int k=i+1;k<=j;k++){int t=m[i][k-1]+m[k+1][j];if(＿＿＿＿＿) {m[i][j]=t; s[i][j]=k;}}m[i][j]=t; s[i][j]=k;}}5、设n=4, (a1,a2,a3,a4)=(3,4,8,10), (b1,b2,b3,b4)=(6,2,9,15) 用两种方法求4个作业的最优调度方案并计算其最优值？（15分）三、简答题（30分）1、将所给定序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有哪三种情形？(10分)答：2、由0——1背包问题的最优子结构性质，可以对m（i,j）建立怎样的递归式? (10分)3、0——1背包求最优值的步骤分为哪几步？（10分）参考答案：填空题：确定性分解成若干个子问题最优解的性质递归地定义最优值以自底向上的方式计算出最优值构造最优解 {i|ai<bi} ai的非减序排序；将N2中作业依bi的非增序排序min{bπ(i),aπ(i+1)}≥min{bπ(i+1),aπ(i)}最小平均查找长度综合题：20 min{ai+T(N-{i},bi)}(1=<i<=n) thissum+=a[k] besti=i 0 m[i+1][j] t<m[i][j]法一：min(ai,bj)<=min(aj,bi)因为 min(a1,b2)<=min(a2,b1)所以 1→2 (先1后2)由 min(a1,b3)<=min(a3,b1)得 1→3 （先1后3）同理可得：最后为1→3→4→2法二：johnson算法思想N1＝{1，3，4} N2＝{2}N¹1＝{1，3，4} N¹2＝{2}所以 N¹1→N¹2得：1→3→4→2简答题：1 、（1）a[1:n]的最大子段和与a[1:n/2]的最大子段和相同。
分治法1、二分搜索算法是利用（分治策略）实现的算法。
9. 实现循环赛日程表利用的算法是（分治策略）27、Strassen矩阵乘法是利用（分治策略）实现的算法。
34．实现合并排序利用的算法是（分治策略）。
实现大整数的乘法是利用的算法（分治策略）。
17．实现棋盘覆盖算法利用的算法是（分治法）。
29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。
不可以使用分治法求解的是（0/1背包问题）。
动态规划下列不是动态规划算法基本步骤的是（构造最优解）下列是动态规划算法基本要素的是（子问题重叠性质）。
下列算法中通常以自底向上的方式求解最优解的是（动态规划法）备忘录方法是那种算法的变形。
（动态规划法）最长公共子序列算法利用的算法是（动态规划法）。
矩阵连乘问题的算法可由（动态规划算法B）设计实现。
实现最大子段和利用的算法是（动态规划法）。
贪心算法能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题，不能解决的问题：N皇后问题，0/1背包问题是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。
回溯法回溯法解旅行售货员问题时的解空间树是（排列树）。
剪枝函数是回溯法中为避免无效搜索采取的策略回溯法的效率不依赖于下列哪些因素（确定解空间的时间）分支限界法最大效益优先是（分支界限法）的一搜索方式。
分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。
分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆）优先队列式分支限界法选取扩展结点的原则是（结点的优先级）在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法).从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法)之外都是最常见的方式.（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。
2.算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是______________________。
3.某一问题可用动态规划算法求解的显著特征是____________________________________。
4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。
5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。
6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。
7.以深度优先方式系统搜索问题解的算法称为_____________。
8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。
9.动态规划算法的两个基本要素是___________和___________。
10.二分搜索算法是利用_______________实现的算法。
二、综合题（50分）1.写出设计动态规划算法的主要步骤。
2.流水作业调度问题的johnson算法的思想。
3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。
4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。
分治算法思想分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。
求出子问题的解，就可得到原问题的解。
即一种分目标完成程序算法，简单问题可用二分法完成。
当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。
对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。
具体介绍：规模为n的原问题的解无法直接求出，进行问题规模缩减，划分子问题。
如果子问题的规模仍然不够小，再进行子问题划分，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止，最后求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。
适用条件有：原问题的规模缩小到一定的程度就可以很容易地解决。
原问题可以分解为若干个规模较小的相同问题，即原问题具有最优子结构性质。
利用原问题分解出的子问题的解可以合并为原问题的解。
原问题分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题（这条特征涉及到分治法的效率，如果各个子问题不独立，也就是子问题划分有重合部分，则分治法要重复的求解1公共子问题的解，此时虽然也可用分治法，但采用动态规划更好）。
特点介绍：原问题可以分解为多个子问题。
这些子问题与原问题相比，只是问题的规模有所降低，其结构和求解方法与原问题相同或相似。
原问题在分解过程中，递归地求解子问题。
由于递归都必须有一个终止条件，因此，当分解后的子问题规模足够小时，应能够直接求解。
在求解并得到各个子问题的解后。
应能够采用某种方式、方法合并或构造出原问题的解。
不难发现，在分治策略中，由于子问题与原问题在结构和解法上的相似性，用分治方法解决的问题，大都采用了递归的形式。
在各种排序方法中，如归并排序、堆排序、快速排序等，都存在有分治的思想。
分治法1、二分搜索算法是利用（分治策略）实现的算法。
9. 实现循环赛日程表利用的算法是（分治策略）27、Strassen矩阵乘法是利用（分治策略）实现的算法。
34．实现合并排序利用的算法是（分治策略）。
实现大整数的乘法是利用的算法（分治策略）。
17．实现棋盘覆盖算法利用的算法是（分治法）。
29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。
不可以使用分治法求解的是（0/1背包问题）。
动态规划下列不是动态规划算法基本步骤的是（构造最优解）下列是动态规划算法基本要素的是（子问题重叠性质）。
下列算法中通常以自底向上的方式求解最优解的是（动态规划法）备忘录方法是那种算法的变形。
（动态规划法）最长公共子序列算法利用的算法是（动态规划法）。
矩阵连乘问题的算法可由（动态规划算法B）设计实现。
实现最大子段和利用的算法是（动态规划法）。
贪心算法能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题，不能解决的问题：N皇后问题，0/1背包问题是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。
回溯法回溯法解旅行售货员问题时的解空间树是（排列树）。
剪枝函数是回溯法中为避免无效搜索采取的策略回溯法的效率不依赖于下列哪些因素（确定解空间的时间）分支限界法最大效益优先是（分支界限法）的一搜索方式。
分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。
分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆）优先队列式分支限界法选取扩展结点的原则是（结点的优先级）在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法).从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法)之外都是最常见的方式.（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。
2.算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是______________________。
3.某一问题可用动态规划算法求解的显著特征是____________________________________。
4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。
5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。
6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。
7.以深度优先方式系统搜索问题解的算法称为_____________。
8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。
9.动态规划算法的两个基本要素是___________和___________。
10.二分搜索算法是利用_______________实现的算法。
二、综合题（50分）1.写出设计动态规划算法的主要步骤。
2.流水作业调度问题的johnson算法的思想。
3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。
4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。
一。
选择题1、二分搜索算法是利用（ A ）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（ D ）。
A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是（ A ）的一搜索方式。
A、分支界限法B、动态规划法C、贪心法D、回溯法5. 回溯法解旅行售货员问题时的解空间树是（）。
A、子集树B、排列树C、深度优先生成树D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。
A、备忘录法B、动态规划法C、贪心法D、回溯法注意：动态规划采用的是自底向上的方式求解，而贪心算法采用的是自顶向下的方式来求解问题。
7、衡量一个算法好坏的标准是（C ）。
A 运行速度快B 占用空间少C 时间复杂度低D 代码短8、以下不可以使用分治法求解的是（D ）。
A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题9. 实现循环赛日程表利用的算法是（ A ）。
A、分治策略B、动态规划法C、贪心法D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。
A、广度优先B、最小耗费优先C、最大效益优先D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。
A、备忘录法B、动态规划法C、贪心法D、回溯法13.备忘录方法是那种算法的变形。
（ B ）A、分治法B、动态规划法C、贪心法D、回溯法注意：备忘录是动态规划方法的一个步骤。
14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。
A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）15．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。
A、最小堆B、最大堆C、栈D、数组16．最长公共子序列算法利用的算法是（ B ）。
A、分支界限法B、动态规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算法是（ A ）。
A、分治法B、动态规划法C、贪心法D、回溯法18.下面是贪心算法的基本要素的是（ C ）。
分治法简介对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
这种算法设计策略叫做分治法。
分治法的基本思想任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。
问题的规模越小，越容易直接求解，解题所需的计算时间也越少。
例如，对于n个元素的排序问题，当n=1时，不需任何计算。
n=2时，只要作一次比较即可排好序。
n=3时只要作3次比较即可，…。
而当n较大时，问题就不那么容易处理了。
要想直接解决一个规模较大的问题，有时是相当困难的。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
如果原问题可分割成k个子问题，1<k≤n ，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。
由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。
这自然导致递归过程的产生。
分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
分治法的适用条件分治法所能解决的问题一般具有以下几个特征：1.该问题的规模缩小到一定的程度就可以容易地解决；2.该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3.利用该问题分解出的子问题的解可以合并为该问题的解；4.该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。
第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
分治法的基本步骤分治法在每一层递归上都有三个步骤：1.分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；2.解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；3.合并：将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下：Divide-and-Conquer(P)1. if |P|≤n02. then return(ADHOC(P))3. 将P分解为较小的子问题P1 ,P2 ,...,P k4. for i←1 to k5. do yi ←Divide-and-Conquer(P i) △递归解决Pi6. T ←MERGE(y1,y2,...,y k) △合并子问题7. return(T)其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。
ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。
因此，当P的规模不超过n0时，直接用算法ADHOC(P)求解。
算法MERGE(y1,y2,...,y k)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,...,P k的相应的解y1,y2,...,y k合并为P的解。
根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难予以肯定的回答。
但人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。
换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。
许多问题可以取k=2。
这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。
分治法的合并步骤是算法的关键所在。
有些问题的合并方法比较明显，如下面的例1，例2；有些问题合并方法比较复杂，或者是有多种合并方案，如例3，例4；或者是合并方案不明显，如例5。
究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。
分治法的复杂性分析从分治法的一般设计模式可以看出，用它设计出的程序一般是一个递归过程。
因此，分治法的计算效率通常可以用递归方程来进行分析。
为方便起见，设分解阈值n0=1，且算法ADHOC解规模为1的问题耗费1个单位时间。
又设分治法将规模为n的问题分成k个规模为n/m的子问题去解，而且，将原问题分解为k个子问题以及用算法MERGE将k个子问题的解合并为原问题的解需用f(n)个单位时间。
如果用T(n)表示该分治法Divide-and-Conquer(P)解规模为|P|=n的问题P所需的计算时间，则有:（1）用算法的复杂性中递归方程解的渐进阶的解法介绍的解递归方程的迭代法，可以求得(1)的解:（2）注意，递归方程(1)及其解(2)只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由等于m的方幂时T(n)的值可以估计T(n)的增长速度。
通常，我们可以假定T(n)是单调上升的，从而当m i≤n<m i+1时，T(m i)≤T(n)<T(m i+1)。
另一个需要注意的问题是，在分析分治法的计算效率时，通常得到的是递归不等式：(3)分治法的几种变形1.二分法dichotomy一种每次将原问题分解为两个子问题的分治法，是一分为二的哲学思想的应用。
这种方法很常用，由此法产生了许多经典的算法和数据结构。
2.分解并在解决之前合并法divide and marriage before conquest一种分治法的变形，其特点是将分解出的子问题在解决之前合并。
3.管道传输分治法pipelined divide and conquer一种分治法的变形，它利用某种称为“管道”的数据结构在递归调用结束前将其中的某些结果返回。
此方法经常用来减少算法的深度。
由于我们关心的一般是最坏情况下的计算时间复杂度的上界，所以用等于号(=)还是小于或等于号(≤)是没有本质区别的。
分治法的实例分析以上讨论的是分治法的基本思想和一般原则，下面我们用具体的例子来说明如何针对具体问题用分治法来设计有效解法。
例1和例2是分治法的经典范例，其分解和合并过程都比较简单明显；例3和例4的合并方法有多种选择，只有选择最好的合并方法才能够改进算法的复杂度；例5是一个计算几何学中的问题，它的合并步骤需要较高的技巧。
例6则是IOI'95的试题Wires and Switches 。
二分查找法Binary Search在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。
此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。
比较自然的想法是一个一个地扫描L的所有元素，直到找到x为止。
这种方法对于有n 个元素的线性表在最坏情况下需要n次比较。
一般来说，如果没有其他的附加信息，在有n 个元素的线性表中查找一个元素在最坏情况下都需要n次比较。
下面我们考虑一种简单的情况。
假设该线性表已经排好序了，不妨设它按照主键的递增顺序排列（即由小到大排列）。
在这种情况下，我们是否有改进查找效率的可能呢？如果线性表里只有一个元素，则只要比较这个元素和x就可以确定x是否在线性表中。
因此这个问题满足分治法的第一个适用条件；同时我们注意到对于排好序的线性表L有以下性质：比较x和L中任意一个元素L[i]，若x=L[i]，则x在L中的位置就是i；如果x<L[i]，由于L是递增排序的，因此假如x在L中的话，x必然排在L[i]的前面，所以我们只要在L[i]的前面查找x即可；如果x>L[i]，同理我们只要在L[i]的后面查找x即可。
无论是在L[i]的前面还是后面查找x，其方法都和在L中查找x一样，只不过是线性表的规模缩小了。
这就说明了此问题满足分治法的第二个和第三个适用条件。
很显然此问题分解出的子问题相互独立，即在L[i]的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。
于是我们得到利用分治法在有序表中查找元素的算法。
function Binary_Search(L,a,b,x);beginif a>b then return(-1)else beginm:=(a+b) div 2;if x=L[m] then return(m)else if x>L[m]then return(Binary_Search(L,m+1,b,x));else return(Binary_Search(L,a,m-1,x));end;end;在以上算法中，L为排好序的线性表，x为需要查找的元素，b,a分别为x的位置的上下界，即如果x在L中，则x在L[a..b]中。
每次我们用L中间的元素L[m]与x比较，从而确定x的位置范围。
然后递归地缩小x的范围，直到找到x。
下面分析该算法的复杂性。
设在n个元素的数组中查找x需要的比较次数为T(n)，如果每次比较x和L[m]时，总有x<>L[m]，即x根本不在L中，则：T(n)=2+T(n/2),T(1)=1该方程的解为T(n)=O(logn)。
所以在最坏情况下二分查找法的复杂度为O(logn)。
快速排序Quick Sort我们已经知道，在决策树计算模型下，任何一个基于比较来确定两个元素相对位置的排序算法需要Ω(nlogn)计算时间。
如果我们能设计一个需要O(n1ogn)时间的排序算法，则在渐近的意义上，这个排序算法就是最优的。
许多排序算法都是追求这个目标。
下面介绍快速排序算法，它在平均情况下需要O(nlogn)时间。
这个算法是由C.A.R.Hoare发明的。
算法的基本思想快速排序的基本思想是基于分治策略的。
对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否则分三步处理：▪分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。
▪递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。
▪合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。
这个解决流程是符合分治法的基本步骤的。
因此，快速排序法是分治法的经典应用实例之一。
