算法（转载百度百科）

╰+攻爆jí腚メ 2022-05-28 10:50 214阅读 0赞

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰[指令][Link 1]，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的[输入][Link 2]，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用[空间复杂度][Link 3]与[时间复杂度][Link 4]来衡量。

一个算法应该具有以下五个重要的特征：

### 有穷性 ###

（Finiteness）

算法的有穷性是指算法必须能在执行有限个步骤之后终止；

### 确切性 ###

(Definiteness)

算法的每一步骤必须有确切的定义；

### 输入项 ###

(Input)

一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；

### 输出项 ###

(Output)

一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

### 可行性 ###

(Effectiveness)

算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。 [算法分析][Link 5]的目的在于选择合适算法和改进算法。一个算法的评价主要从 [时间复杂度][Link 4]和 [空间复杂度][Link 3]来考虑。

### 时间复杂度 ###

算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做。

T(n)=Ο(f(n))

因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作 [渐进时间复杂度][Link 6]（Asymptotic Time Complexity）。

### 空间复杂度 ###

算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间 [复杂度][Link 7]类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

### 正确性 ###

算法的正确性是评价一个算法优劣的最重要的标准。

### 可读性 ###

算法的可读性是指一个算法可供人们阅读的容易程度。  \[1\]

### 健壮性 ###

\[1\]

健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也称为 容错性。

### 递推法 ###

递推是 [序列][Link 8] [计算机][Link 9]中的一种常用算法。它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的 [庞大][Link 10]的计算过程转化为 [简单][Link 11] [过程][Link 12]的多次 [重复][Link 13]，该算法利用了计算机速度快和 [不知疲倦][Link 14]的机器特点。

### 递归法 ###

程序调用自身的编程技巧称为 [递归][Link 15]（recursion）。一个过程或 [函数][Link 16]在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的 [语句][Link 17]来定义对象的 [无限集合][Link 18]。一般来说，递归需要有 [边界条件][Link 19]、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

注意：

(1) 递归就是在过程或 [函数][Link 16]里调用自身;

(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

### 穷举法 ###

[穷举法][Link 20]，或称为 [暴力破解][Link 21]法，其基本思路是：对于要解决的问题，列举出它的所有可能的情况，逐个判断有哪些是符合问题所要求的条件，从而得到问题的解。它也常用于对于 [密码][Link 22]的 [破译][Link 23]，即将密码进行逐个推算直到找出真正的密码为止。例如一个已知是四位并且全部由数字组成的密码，其可能共有10000种组合，因此最多尝试10000次就能找到正确的密码。理论上利用这种方法可以破解任何一种密码，问题只在于如何缩短试误时间。因此有些人运用计算机来增加效率，有些人辅以字典来缩小 [密码][Link 22]组合的范围。

### 贪心算法 ###

[贪心算法][Link 24]是一种对某些求最优解问题的更 [简单][Link 11]、更迅速的设计技术。

用贪心法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找 [最优解][Link 25]要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。

[贪婪算法][Link 26]是一种改进了的分级处理方法，其核心是根据题意选取一种量度标准，然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量，如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个 [可行解][Link 27]，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。

对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。

一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。

### 分治法 ###

[分治法][Link 28]是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治法所能解决的问题一般具有以下几个特征：

(1) 该问题的规模缩小到一定的程度就可以容易地解决；

(2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；

(3) 利用该问题分解出的子问题的解可以合并为该问题的解；

(4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

### 动态规划法 ###

[动态规划][Link 29]是一种在数学和 [计算机科学][Link 30]中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种 [最优化问题][Link 31]，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。

### 迭代法 ###

[迭代法][Link 32]也称 [辗转][Link 33] [法][Link 34]，是一种不断用变量的旧值 [递推][Link 35]新值的过程，跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“ [二分法][Link 36]”和“ [牛顿迭代法][Link 37]”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

### 分支界限法 ###

[分枝界限法][Link 38]是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。

分支定界法的基本思想是对有 [约束条件][Link 39]的 [最优化问题][Link 31]的所有 [可行解][Link 27]（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的 [解空间][Link 40]不断分割为越来越小的 [子集][Link 41]（称为分支），并为每个子集内的解的值计算一个下界或 [上界][Link 42]（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支，这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出 [可行解][Link 27]为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得 [最优解][Link 25]。

与 [贪心算法][Link 24]一样，这种方法也是用来为 [组合][Link 43] [优化][Link 44]问题设计求解算法的，所不同的是它在问题的整个可能解空间搜索，所设计出来的算法虽其 [时间复杂度][Link 4]比 [贪婪算法][Link 26]高，但它的优点是与 [穷举法][Link 20]类似，都能保证求出问题的最佳解，而且这种方法不是盲目的穷举搜索，而是在搜索过程中通过 [限界][Link 45]，可以中途停止对某些不可能得到最优解的子空间进一步搜索（类似于人工智能中的剪枝），故它比穷举法 [效率][Link 46]更高。

### 回溯法 ###

回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个 [状态][Link 47]的点称为“回溯点”。

其基本思想是，在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束

[Link 1]: https://baike.baidu.com/item/%E6%8C%87%E4%BB%A4
[Link 2]: https://baike.baidu.com/item/%E8%BE%93%E5%85%A5
[Link 3]: https://baike.baidu.com/item/%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6
[Link 4]: https://baike.baidu.com/item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6
[Link 5]: https://baike.baidu.com/item/%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90
[Link 6]: https://baike.baidu.com/item/%E6%B8%90%E8%BF%9B%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6
[Link 7]: https://baike.baidu.com/item/%E5%A4%8D%E6%9D%82%E5%BA%A6
[Link 8]: https://baike.baidu.com/item/%E5%BA%8F%E5%88%97/1302588
[Link 9]: https://baike.baidu.com/item/%E8%AE%A1%E7%AE%97%E6%9C%BA
[Link 10]: https://baike.baidu.com/item/%E5%BA%9E%E5%A4%A7/16883
[Link 11]: https://baike.baidu.com/item/%E7%AE%80%E5%8D%95/2903
[Link 12]: https://baike.baidu.com/item/%E8%BF%87%E7%A8%8B
[Link 13]: https://baike.baidu.com/item/%E9%87%8D%E5%A4%8D/33187
[Link 14]: https://baike.baidu.com/item/%E4%B8%8D%E7%9F%A5%E7%96%B2%E5%80%A6
[Link 15]: https://baike.baidu.com/item/%E9%80%92%E5%BD%92
[Link 16]: https://baike.baidu.com/item/%E5%87%BD%E6%95%B0
[Link 17]: https://baike.baidu.com/item/%E8%AF%AD%E5%8F%A5
[Link 18]: https://baike.baidu.com/item/%E6%97%A0%E9%99%90%E9%9B%86%E5%90%88
[Link 19]: https://baike.baidu.com/item/%E8%BE%B9%E7%95%8C%E6%9D%A1%E4%BB%B6
[Link 20]: https://baike.baidu.com/item/%E7%A9%B7%E4%B8%BE%E6%B3%95
[Link 21]: https://baike.baidu.com/item/%E6%9A%B4%E5%8A%9B%E7%A0%B4%E8%A7%A3
[Link 22]: https://baike.baidu.com/item/%E5%AF%86%E7%A0%81
[Link 23]: https://baike.baidu.com/item/%E7%A0%B4%E8%AF%91
[Link 24]: https://baike.baidu.com/item/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95
[Link 25]: https://baike.baidu.com/item/%E6%9C%80%E4%BC%98%E8%A7%A3
[Link 26]: https://baike.baidu.com/item/%E8%B4%AA%E5%A9%AA%E7%AE%97%E6%B3%95
[Link 27]: https://baike.baidu.com/item/%E5%8F%AF%E8%A1%8C%E8%A7%A3
[Link 28]: https://baike.baidu.com/item/%E5%88%86%E6%B2%BB%E6%B3%95
[Link 29]: https://baike.baidu.com/item/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92
[Link 30]: https://baike.baidu.com/item/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6
[Link 31]: https://baike.baidu.com/item/%E6%9C%80%E4%BC%98%E5%8C%96%E9%97%AE%E9%A2%98
[Link 32]: https://baike.baidu.com/item/%E8%BF%AD%E4%BB%A3%E6%B3%95
[Link 33]: https://baike.baidu.com/item/%E8%BE%97%E8%BD%AC
[Link 34]: https://baike.baidu.com/item/%E6%B3%95/34274
[Link 35]: https://baike.baidu.com/item/%E9%80%92%E6%8E%A8
[Link 36]: https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E6%B3%95
[Link 37]: https://baike.baidu.com/item/%E7%89%9B%E9%A1%BF%E8%BF%AD%E4%BB%A3%E6%B3%95
[Link 38]: https://baike.baidu.com/item/%E5%88%86%E6%9E%9D%E7%95%8C%E9%99%90%E6%B3%95
[Link 39]: https://baike.baidu.com/item/%E7%BA%A6%E6%9D%9F%E6%9D%A1%E4%BB%B6
[Link 40]: https://baike.baidu.com/item/%E8%A7%A3%E7%A9%BA%E9%97%B4
[Link 41]: https://baike.baidu.com/item/%E5%AD%90%E9%9B%86
[Link 42]: https://baike.baidu.com/item/%E4%B8%8A%E7%95%8C
[Link 43]: https://baike.baidu.com/item/%E7%BB%84%E5%90%88
[Link 44]: https://baike.baidu.com/item/%E4%BC%98%E5%8C%96
[Link 45]: https://baike.baidu.com/item/%E9%99%90%E7%95%8C
[Link 46]: https://baike.baidu.com/item/%E6%95%88%E7%8E%87
[Link 47]: https://baike.baidu.com/item/%E7%8A%B6%E6%80%81