算法

算法（英语：algorithm），在数学（算学）和电脑科学之中，指一个被定义好的、计算机可施行其指示的有限步骤或次序，常用于计算、数据处理（英语：Data processing）和自动推理。算法是有效方法（英语：Effective method），包含一系列定义清晰的指令，并可于有限的时间及空间内清楚的表述出来。

特征

以下是高德纳在他的著作《计算机程序设计艺术》里对演算法的特征归纳：

• 输入：一个算法必须有零个或以上输入量。
• 输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。
• 明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确地符合要求或期望，通常要求实际执行结果是确定的。
• 有限性：依据图灵的定义，一个演算法是能够被任何图灵完备系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定演算法必须在有限个步骤内完成任务。
• 有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

基本要素

算法的核心是建立问题抽象的模型和明确求解目标，之后可以根据具体的问题选择不同的模式和方法完成算法的设计。

常用设计模式

• 完全遍历法和不完全遍历法：在问题的解是有限离散解空间，且可以验证正确性和最优性时，最简单的算法就是把解空间的所有元素完全遍历一遍，逐个检测元素是否是我们要的解。这是最直接的算法，实现往往最简单。但是当解空间特别庞大时，这种算法很可能导致工程上无法承受的计算量。这时候可以利用不完全遍历方法 —— 例如各种搜索法和规划法 —— 来减少计算量。

• 分治法：把一个问题分割成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。

• 动态规划法：当问题的整体最优解就是由局部最优解组成的时候，经常采用的一种方法。

• 贪婪算法：常见的近似求解思路。当问题的整体最优解不是（或无法证明是）由局部最优解组成，且对解的最优性没有要求的时候，可以采用的一种方法。

• 线性规划法：指目标函数和约束条件皆为线性的最佳化问题。。

• 简并法：把一个问题通过逻辑或数学推理，简化成与之等价或者近似的、相对简单的模型，进而求解的方法。

常用实现方法

• 递归方法与迭代方法

• 顺序计算、并行计算和分布式计算：顺序计算就是把形式化算法用编程语言进行单线程序列化后执行。

• 确定性算法和非确定性算法

• 精确求解和近似求解

复杂度

时间复杂度

算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法是问题规模 n 的函数${\displaystyle f(n)}$，算法的时间复杂度也因此记做$T(n)=\mathcal{O}(f(n))$。

算法执行时间的增长率与${\displaystyle f(n)}$ 的增长率正相关，称作渐近时间复杂度（英语：Asymptotic computational complexity），简称时间复杂度。

常见的时间复杂度有：常数阶${\displaystyle O(1)}$，对数阶${\displaystyle O(\log n)}$，线性阶${\displaystyle O(n)}$，线性对数阶${\displaystyle O(n\log n)}$，平方阶$O(n^{2})$，立方阶${\displaystyle O(n^{3})}$，...， k 次方阶${\displaystyle O(n^{k})}$, 指数阶${\displaystyle O(2^{n})}$。随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

空间复杂度

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

参考

• 算法 - Wikiwand (opens new window)