算法的大致分类（算法的三种基本要素） - 原点资讯

算法可以理解为问题求解解决方案（方法和步骤）的描述。准确地说，是一组明确步骤的有序集合，它产生结果并在有限的时间内终止。是问题域到指令集的映射，中间可以有若干抽象层。为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，或者说效率或性能。

在任何一个程序中，算法无处不在（表现为函数或类方法）。或经典，复用率高，或普通，利用率低。

在程序内，算法无处不在（用某种编程语言的函数来描述），或大或小，或复杂或简单，或复用性高或复用性低。与数据结构也有千丝万缕的关系。如何理解算法呢？可以从算法分类入手，在整体上把握其全貌，再去了解其细节。因为从方法论来说，理解一复杂事物，需要从整体与细节两个方面的视点，交叉去深入了解，避免盲人摸象，避免只见树木，不见森林。

1 与数据结构相关的算法和独立于数据结构的算法

我们知道，计算机的计算不单纯只是数值的计算，很大一部分是非数值的数据处理（称为非数值算法），这一部分的数据就涉及到数据结构的概念。

算法的大致分类,算法的三种基本要素(1)

算法与数据结构相互影响。选择合适的数据结构，直接关乎的算法的选择，同时，选择的算法又会反过来影响数据结构的选择，有时，就是这样反复影响，来找到最佳的数据结构与算法的匹配。

算法的大致分类,算法的三种基本要素(2)

2 经典算法思想

经典的算法总是以经典的算法思想为指导：

算法的大致分类,算法的三种基本要素(3)

2.1 大事化小的算法思想

2.1.1 分治法

分治法解为独立的子问题（Divide），解决（solve），合并（combine）（如果需要），如快速排序、折半查找（可以循环迭代实现，也可以递归实现）。

在分治算法中，各个子问题形式相同，解决的方法也一样，因此我们可以使用递归算法快速解决，递归是彰显分治法优势的利器。

除了分治法，还有减治法、变治法的说法。
减治法是利用一个问题给定实例的解和同样问题较小实例的解之间的关系。一旦建立了这样一种关系，我们既可以自顶至下（递归）也可以自底至上地运用它（非递归）。典型实例如阶乘。
变治法是一组基于变换思想的技术，用来把问题变换成一种更容易解决的类型。如有最简单的实例如最大公约数的辗转求法。
变治技术有三种主要的类型：实例化简、改变表现和问题化简。
实例化简是一种把问题的实例变换成相同问题的另一个实例的技术，这个新的实例有一些特殊的属性，使得它更容易被解决。列表预排序、高斯消去法和AVL 树都是这种技术的好例子。
改变表现指的是将一个问题实例的表现改变为同样实例的另一种表现。如用2－3树表示集合、堆和堆排序、求多项式的霍纳法则以及两种二进制幂算法。
问题化简提倡把一个给定的问题变换为另一个可以用已知算法求解的问题。如那些化简为线性规划问题和化简为图问题是尤其重要的。

2.1.2 动态规划法

动态规划法问题重叠或不独立，无后效性，分阶段递推，如利用额外数组求解斐波那契问题。

动态规划是1957年理查德·贝尔曼在Dynamic Programming一书中提出来的。“Programming”不是编程的意思，而是指一种表格处理法。我们把每一步得到的子问题结果存储在表格里，每次遇到该子问题时不需要再求解一遍，只需要查询表格即可。

求解动态规划问题，如何确定状态和转移方程是关键，也是难点。不同的状态和转移方程可能导致不同的算法复杂度。

2.1.3 贪婪法

贪婪法具有最优子结构，不回溯（一旦选择，不再反悔），堆叠；如背包问题，最优装载问题，最短路径问题、哈夫曼编码最小生成树。

贪心选择性质是指原问题的整体最优解可以通过一系列局部最优的选择得到。将原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。

2.1.4 三类大事化小的算法思想的比较

动态规划也是一种分治思想，但与分治算法不同的是，分治算法是把原问题分解为若干子问题，自顶向下求解各子问题，合并子问题的解，从而得到原问题的解。动态规划也是把原问题分解为若干子问题，然后自底向上，先求解最小的子问题，把结果存储在表格中，再求解大的子问题时，直接从表格中查询小的子问题的解，避免重复计算，从而提高算法效率。贪心法与动态规划法一样，都具有最优子结构。

2.2 解空间枚举的算法思想

2.2.1 回溯法

回溯法是以深度优先（DFS，以栈辅助实现）（或递归）的方式搜索问题的解空间来求最优解，如分书问题、n皇后问题。

回溯法是按照深度优先搜索策略，根据隐约束（约束函数和限界函数），在解空间中搜索问题的可行解或最优解，当发现当前结点不满足求解条件时，就回溯尝试其他的路径。

回溯法是一种“能进则进，进不了则换，换不了则退”的搜索方法。

隐约束（剪枝函数）包括约束函数和限界函数。

对能否得到问题的可行解的约束称为约束函数，对能否得到最优解的约束称为限界函数。剪枝函数可以剪掉得不到可行解或最优解的分支，避免无效搜索，提高搜索的效率。剪枝函数设计得好，搜索效率就高。

如果问题只是要求可行解，则只需要设定约束函数即可，如果要求最优解，则需要设定约束函数和限界函数。

2.2.1 分支限界法

分支限界法是以广度优先（BFS，以队列辅助实现）的方式搜索问题的解空间来求最优解，如电路板布线问题。

搜索前要定义判断标准（约束函数或限界函数）。

解空间的大小和剪枝函数的好坏都直接影响搜索效率，因此这两项是搜索算法的关键。

2.3 递归与上述算法思想的结合

2.3.1 递归与迭代

迭代：反复利用变量旧值推出新值

折半查找（迭代）
归并查找（迭代）

2.3.2 递归与分治

分治法：问题的分解，问题规模的分解。

折半查找（递归）
归并查找（递归）
快速排序（递归）

2.3.3 递归与回溯法

直接枚举法的优点是思路和程序都很简单，缺点在于无法简便地减小枚举量——必须生成（generate）所有可能的解，然后一一检查（test）。

当把问题分成若干步骤并递归求解时，如果当前步骤没有合法选择，则函数将返回上一级递归调用，这种现象称为回溯。正是因为这个原因，递归枚举算法常被称为回溯法，应用十分普遍。

回溯法（backtracking）中，生成和检查过程可以有机结合起来，从而减少不必要的枚举。在某种情况下，递归函数将不再递归调用它自身，而是返回上一层调用，这种现象称为回溯（backtracking）。

递归与回溯的共通点是两者都要考虑回归，所以一些回溯法可以很方便地很递归法去实现。

不考虑回归	考虑回归（隐式或显式栈）
递推	递归
贪心算法	回溯法

递归与回溯：

void recursion() { if( test for simple case) Compute a simple solution without using recursion. else { 1 Break the problem down into subproblems of the same form. 2 Solve each of the subproblems by calling this function recursively. 3 Reassemble the subproblem solutions into a solution for the whole. } } void Backtracking() { If you are already at a solution, Report success. for ( every possible choice in the current position ) { 1 Make that choice and take one step along the path. 2 Use recursion to solve the problem from the new position. 3 If the recursive call succeeds, report the success to the next higher level. 4 If not, back out of the current choice to restore the previous state. } Report failure. }

2.4 经典问题与经典算法思想的结合

如背包问题就是一个经典的问题，可以使用多种算法思想来考虑这一问题的解法。

算法的大致分类,算法的三种基本要素(4)

3 其它的一些经典算法类别

如遗传算法、模拟算法。

数值算法：概率算法、高精度算法、排列组合问题相关的算法等。

4 经典领域的经典算法

数据处理有两个经典领域：排序、查找，涉及到大量算法算法的运用。

冒泡排序	顺序查找
选择排序	二分查找
插入排序	三分查找
希尔排序	分块查找
归并排序	B树查找
快速排序	哈希查找
计数排序	插值查找
基数排序	树表查找
拓扑排序	z字符串查找
桶排序	斐波那契查找
堆排序	KMP字符串查找
圈排序	Rabin-Karp字符串查找
梳排序	A*搜索
基数排序	深度优先搜索
鸽巢排序	广度优先搜索
煎饼排序
二叉树排序
鸡尾酒排序