《算法设计与分析》课程已经进入尾声，在这里对学过的算法进行总结归纳。笔者先对各个算法的思想进行简单的陈述，然后再进行对比。

一、算法思想

（一）分治法（divide and conquer method）

是 将待求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解 。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止（子问题求解思路一致），再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。

（二）动态规划法（dynamic programing method）

动态规划，当前子问题的解将由上一次子问题的解推算出 。

动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。在这种情况下，分治算法会做出许多不必要的工作，它会反复的求解那些公共子问题，而动态规划对每一个子子问题只求解一次，将结果保存到数组中，从而在下次使用时，直接从数组中得到，无需每次求解一个子子问题时都要重复计算公共子子问题。

（三）贪心法（greedy method）

贪心法并不是从整体最优考虑，它 所做出的选择只是在某种意义上的局部最优。 这种局部最优选择并不总能获得整体最优解（Optimal Solution），但通常能获得近似最优解（Near-Optimal Solution）。

（四）回溯法（back track method）

回溯法采用深度优先方法搜索遍历问题的解空间 ，可以看作是蛮力法穷举搜索的改进。先判断该节点对应的部分是否是满足约束条件，也就是判断该节点是否包含问题的最优解。如果肯定不包含，则跳过对该节点为根的子树的搜索，即所谓的剪枝；否则，进入该节点为根的子树，继续按照深度优先策略搜索。回溯法常常可以避免搜索所有可能的解，所以，适用于求解组合数组较大的问题。

（五）分支限界法（branch and bound method）

分支限界法按广度优先策略遍历问题的解空间 ，在遍历过程中，对已经处理的每一个结点根据限界函数估算目标函数的可能值，从中选取使目标函数取得极值（极大或极小）的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。因为界限函数常常是基于问题的目标函数而确定的，所以，分支限界法适用于求解最优化问题。

二、算法差异

（一）分治法和动态规划法的区别

共同点：二者都要求原问题具有最优子结构性质，都将原问题分成若干个子问题，然后将子问题的解合并，形成原问题的解。

不同点：动态规划法是将待求解问题分解成若干个相互重叠的子问题，即不同的子问题具有公共的子子问题，而分治法是分解成若干个互不相交的子问题。利用分治法求解，这些子问题的重叠部分被重复计算多次。而动态规划法将每个子问题只求解一次并将其保存在一个数组中，当需要再次求解此子问题时，从数组中获得该子问题的解，从而避免了大量的重复计算。

（二）动态规划法和贪心法的区别

共同点：贪心算法和动态规划算法都要求问题具有最优子结构性质。

不同点：动态规划法用到之前的最优解，贪心则不是，贪心无法解决动态规划的问题，但是动态规划能解决贪心的问题。虽然能够应用贪心算法一定能够应用动态规划法，但是一般来说，贪心算法的效率高于动态规划法，因而还是应用贪心算法。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。

（三）回溯法和分支限界法的区别

共同点：一种在问题的解空间树上搜索问题解的算法。

不同点：求解目标不同，回溯法的目标是找出解空间树满足约束条件的所有解，而分支限界法的求解目标是尽快地找出满足约束条件的一个解；搜索方法不同，回溯法采用深度优先方法搜索解空间，而分支限界法一般采用广度优先或以最小消耗优先的方式搜索解空间树；对扩展结点的扩展方式不同，回溯法中，如果当前的扩展结点不能够再向纵深方向移动，则当前扩展结点就成为死结点，此时应回溯到最近一个活结点处，并使此活结点成为扩展结点。分支限界法中，每一次活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点；存储空间的要求不同，分支限界法的存储空间比回溯法大得多，当内存容量有限时，回溯法成功的可能性更大。

三、适用情况

(一)分治法

适用特征：该问题的规模缩小到一定的程度就可以容易地解决；可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；利用该问题分解出的子问题的解可以合并为该问题的解；所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

典型代表：二分搜索、棋盘覆盖、合并排序、最接近点对问题、循环赛日程表、汉诺塔......

(二)动态规划法

适用特征：该问题问题的最优解所包含的子问题的解也是最优的，即满足最优化原理；某状态以后的过程不会影响以前的状态，只与当前状态有关；子问题之间是不独立的，当前子问题的解将由上一次子问题的解推算出。

典型代表：最长公共子序列、最优二叉查找树、近似串匹配问题、背包问题、......

(三)贪心法

适用特征：该问题局部最优策略能导致产生全局最优解（贪心算法适用的情况很少）。

典型代表：TSP问题（最近邻点）、TSP问题（最短链接）、图着色、多极度调度问题......

(四)回溯法

适用特征：该问题是求解组合数量较大；需要找出该问题的解集（全部解）或者要求回答什么解是满足某些约束条件的最优解。

典型代表：哈密顿回路问题、八皇后问题、批处理作业调度......

(五)分支限界法

适用特征：求解最优化问题。

典型代表：单源最短路径问题、批处理作业调度问题、电路布线问题

这篇文章目的是分析 算法 的复杂度问题，关于 算法 的定义、特性等等问题在这里不作讲解。 如何度量 算法 效率 我们知道， 算法 是解决复杂问题的思路，条条大路通罗马，对于一个复杂的问题，能够解决的 算法 也有很多种，对于有多种解决方案的 情况 ，我们当然是想选择一种快速、有效的 算法 了。那么我们该如何知晓一个 算法 的效率呢？ 1、事后统计 法 该方 法 通过设计好的测试程序和数据，然后在计算机中运行，接着对运行时间进行比较，耗时... 1. 分治 分治法 的设计思想是，将一个难以直接解决的大问题，分割成k个规模较小的子问题，这些子问题相互独立，且与原问题相同，然后各个击破，分而治之。 分治法 常常与递归结合使用：通过反复应用 分治 ，可以使子问题与原问题类型一致而规模不断缩小，最终使子问题缩小到很容易求出其解，由此自然导致递归 算法 。 根据 分治法 的分割原则，应把原问题分割成多少个子问题才比较适宜？每... 算法 分析几个常用到的级数： 1、算术级数(等差数列)： T(n)=1+2+3+...+n=n(n+1)/2=O(n2)T(n) = 1+2+3+...+n = n(n+1)/2 =O(n^2)T(n)=1+2+3+...+n=n(n+1)/2=O(n2) 2、幂方级数，结果比幂次高一阶： T2(n)=12+22+32+...+n2=n(n+1)(2n+1) 动态规划 法 是通过把原问题分解为相对简单的子问题的方式求解复杂问题的方 法 。与 分治法 不同的是， 动态规划 解决的子问题往往不是互相独立的，即不同的子问题之间可能共享一些子子问题的解。 动态规划 通过存储这些子问题的解来避免重复计算，从而提高效率。 一、 贪心法 贪心 算法 的定义： 贪心 算法 （也叫贪婪 算法 ）是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。 贪心 算法 不是对所有问题都能得到全局最优解，得到的是局部最优解，关键是 贪心 策略的选择，不同的贪婪策略会导致得到差异非常大的结果。选择的 贪心 策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。 解题的一般... 递推 法 是利用问题本身所具有的一种递推关系求问题解的一种方 法 。它把问题分成若干步，找出相邻几步的关系，从而达到目的，此方 法 称为递推 法 。 递归指的是一个过程：函数不断引用自身，直到引用的对象已知 3.穷举搜索 法 穷举搜索 法 是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。 4.贪婪 法 (又称 （2）它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。 （3）一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，... 动态规划 问题一般形式就是求最值（最长递增子序列、最小编辑距离） 其本质就是穷举，但不是暴力穷举，其思想源于暴力穷举，但使用了“备忘录”或DP Table进行优化，此外再无奥妙可言（思考如何穷举->追求聪明地穷举） ps. 以后看到求最值问题，养成条件反射：首先思考如何穷举所有可能结果 动态规划 三要素：重叠子问题、最优子结构、状态转移方程 有重叠子问题决定了 动态规划 与暴力穷举的不同， 动态规划 能使用“备忘录”或DP Table进行优化   穷举 法 简单粗暴，没有什么问题是搞不定的，只要你肯花时间。同时对于小数据量，穷举 法 就是最优秀的 算法 。 二 、 贪心 算法 利用局部最优解当作是问题的答案，只要找到符合条件的其中一种 情况 ， 同时该解并不一定是全局最优解。每一步都将最好的结果保存起来，结合起来作为最终答案。 三、 分治 算法 分治 算法 是将一个大问题，分解为若干的子问题，并且每个子问题之间没有交集，相互独立，所有子问题的答案组合起来构成大问题的解答。分支 算法 的实现方式采用递归实现。   例如 二 分查找、快速排序和归并排序 算法 ： ht