算法

算法（英語：algorithm），在數學（算學）和電腦科學之中，指一個被定義好的、計算機可施行其指示的有限步驟或次序^[1]，常用於計算、數據處理（英语：Data processing）和自動推理。算法是有效方法（英语：Effective method），包含一系列定义清晰的指令^[2]，并可于有限的时间及空间内清楚的表述出来^[3]。

应对灯泡不亮的简单算法流程图

算法中的指令描述的是一個計算，它執行（英语：Execution (computing)）時從一個初始狀態和初始輸入（可能爲空）開始，^[4]經過一系列有限^[5]而清晰定義的狀態最終產生輸出^[6]並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。包括隨機化算法在内的一些算法，都包含了一些隨機輸入。^[7][8]

早在尝试解决希尔伯特提出的判定问题时，算法的不完整概念已经初步定型；在其后的正式化阶段中人們尝试去定义“有效可計算性（英语：Effective calculability）^[9]”或者“有效方法（英语：Effective method）^[10]”。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年埃米爾·萊昂·珀斯特（英语：Emil Leon Post）的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當下，依然常有符合直覺的想法難以定義爲形式化算法的情況。^[11]

历史

算法在中国古代文献中称为“术”，最早出现在《周髀算經》、《九章算术》。特别是《九章算术》，给出四则运算、最大公约数、最小公倍数、开平方根、开立方根、求素数的埃氏篩，线性方程组求解的高斯消元法。三国時代的刘徽给出求圆周率的算法：刘徽割圆术。

自唐代以来，历代更有许多专门论述“算法”的专著：

• 唐代：《一位算法》 一卷，《算法》 一卷；
• 宋代：《算法绪论》 一卷、《算法秘诀》 一卷；最著名的是杨辉的《杨辉算法》；
• 元代：《丁巨算法》；
• 明代：程大位 《算法统宗》
• 清代：《开平算法》、《算法一得》、《算法全书》。

而英文名稱「algorithm」来自于9世纪波斯数学家花拉子米（比阿勒·霍瓦里松，波斯語：خوارزمی ‎，拉丁轉寫：al-Khwarizmi），因為比阿勒·霍瓦里松在数学上提出了算法这个概念。「算法」原为「algorism」，即“al-Khwarizmi”的音转，意思是“花拉子米”的运算法则，在18世纪演变为「algorithm」。

欧几里得算法被人们认为是史上第一个算法。

第一次编写程序是愛達·勒芙蕾絲（Ada Byron）于1842年为巴贝奇分析机编写求解解伯努利微分方程的程序，因此愛達·勒芙蕾絲被大多数人认为是世界上第一位程序员^[12]。因为查尔斯·巴贝奇（Charles Babbage）未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。

因为「well-defined procedure」缺少数学上精确的定义，19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要的作用。

特征

以下是高德纳在他的著作《计算机程序设计艺术》裡對演算法的特徵歸納：

 

1. 输入：一个算法必须有零个或以上输入量。
2. 输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。
3. 明確性：算法的描述必须无歧义，以保证算法的實際执行结果是精確地符合要求或期望，通常要求實際執行結果是确定的。
4. 有限性：依據圖靈的定義，一個演算法是能夠被任何圖靈完備系統模擬的一串運算，而圖靈機只有有限個狀態、有限個輸入符號和有限個轉移函數（指令）。而一些定義更規定演算法必须在有限個步骤内完成任務。
5. 有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

基本要素

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

常用设计模式

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

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

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

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

线性规划法：见条目。

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

常用实现方法

递归方法与迭代方法

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

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

精确求解和近似求解

形式化算法

算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。

复杂度

时间复杂度

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

${\displaystyle 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)}$ ，平方阶${\displaystyle O(n^{2})}$ ，立方阶${\displaystyle O(n^{3})}$ ，...，${\displaystyle k}$ 次方阶${\displaystyle O(n^{k})}$ ,指数阶${\displaystyle O(2^{n})}$ 。随着问题规模${\displaystyle n}$ 的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

空间复杂度

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

非確定性多項式時間（NP）

主条目：NP (複雜度)

实现

算法不单单可以用计算机程序来实现，也可以在人工神经网络、电路或者机械设备上实现。

範例

求最大值演算法

这是算法的一个简单的例子。

我们有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数字看成是一颗豆子的大小，可以将下面的算法形象地称为「捡豆子」：

1. 首先将第一颗豆子放入口袋中。
2. 从第二颗豆子开始检查，如果正在检查的豆子比口袋中的还大，则将它捡起放入口袋中，同时丢掉原先口袋中的豆子。反之則繼續下一顆豆子。直到最后一颗豆子。
3. 最后口袋中的豆子就是所有的豆子中最大的一颗。

以上算法在中国大陆的教科书中通常被叫做“打擂法”或者“循环打擂”^[13][14][15]：在一个for循环中，每轮循环都有新的挑战者。若挑战者胜的话，挑战者做新擂主，否则擂主卫冕。for循环结束后输出最后的擂主。

下面是一个形式算法，用ANSI C代码表示

int max(int *array, int size) {  int mval = *array;  int i;  for (i = 1; i < size; i++)  if (array[i] > mval)  mval = array[i];  return mval; } 

求最大公約數演算法

求两个自然数的最大公约数 设两个变量${\displaystyle M}$ 和${\displaystyle N}$ 

1. 如果${\displaystyle M<N}$ ，则交换${\displaystyle M}$ 和${\displaystyle N}$ 
2. ${\displaystyle M}$ 除以${\displaystyle N}$ ，得到余数${\displaystyle R}$ 
3. 判断${\displaystyle R=0}$ ，正确则${\displaystyle N}$ 即为“最大公约数”，否则下一步
4. 将${\displaystyle N}$ 赋值给${\displaystyle M}$ ，将${\displaystyle R}$ 赋值给${\displaystyle N}$ ，重做第一步。

用ANSI C代码表示

//交換2數 void swapi(int *x, int *y) {  int tmp = *x;  *x = *y;  *y = tmp; } int gcd(int m, int n) {  int r;  do  {  if (m < n)  swapi(&m, &n);  r = m % n;  m = n;  n = r;  } while (r);  return m; } 

利用if函式以及遞迴則能做出更為精簡的程式碼，更可省去交換的麻煩。（但是也因為遞迴呼叫，其空間複雜度提高）

int gcd(int a,int b) {  if(a%b)  return gcd(b,a%b);  return b; } 

分类

• 基本算法
  • 枚举
  • 搜索
    • 深度优先搜索
    • 广度优先搜索
    • 启发式搜索
    • 遗传算法
• 数据结构的算法
• 数论与代数算法
• 计算几何的算法
  • 凸包算法
• 图论的算法
  • 哈夫曼编码
  • 树的遍历
  • 最短路径算法
  • 最小生成树算法
  • 最小树形图
  • 网络流算法
  • 匹配算法
  • 分團問題
• 动态规划
• 其他
  • 数值分析
  • 加密算法
  • 排序算法
  • 检索算法
  • 随机化算法
  • 关于并行算法，请参阅并行计算一文。

註釋

1. Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein; 殷建平等译. 第1章 算法在计算机中的作用. 算法导论 原书第3版. 北京: 机械工业出版社. 2013年1月: 3[5] [2017-11-14]. ISBN 978-7-111-40701-0 （中文）.  引文使用过时参数coauthors (帮助)
2. Well defined with respect to the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations"（Rogers 1987:2）.
3. "Any classical mathematical algorithm, for example, can be described in a finite number of English words"（Rogers 1987:2）.
4. "An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins"（Knuth 1973:5）
5. "A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method'"（Knuth 1973:5）
6. "An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs"（Knuth 1973:5）
7. Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices... carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2).
8. Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices ... carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2).
9. Kleene（斯蒂芬·科尔·克莱尼）1943 in Davis 1965:274
10. Rosser（巴克利·羅瑟）1939 in Davis 1965:225
11. Moschovakis, Yiannis N. What is an algorithm?. Engquist, B.; Schmid, W. (编). Mathematics Unlimited—2001 and beyond. Springer. 2001: 919–936 (Part II) [2012-09-27]. （原始内容于2021-04-24）. 
12. Ada Lovelace honoured by Google doodle. The Guardian. 10 December 2012 [10 December 2012]. （原始内容于2018-12-25）. 
13. . 读书频道-IT技术图书-51CTO.COM. [2017-06-07]. （原始内容存档于2017-03-24）. 
14. 实验3-9：循环打擂. 湖南科技大学程序设计在线评测（Online Judge）. ^{[永久失效連結]}
15. . 在点网. [2017-06-07]. （原始内容存档于2019-06-03）. 

参考文献

• Rogers, Jr, Hartley. Theory of Recursive Functions and Effective Computability. The MIT Press. 1987. ISBN 0-262-68052-1. 
• Davis, Martin. The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions. New York: Raven Press. 1965. ISBN 0-486-43228-9.  Davis此書中有列出許多相關的論文，包括哥德尔、邱奇、图灵、巴克利·羅瑟（英语：Rosser）、斯蒂芬·科尔·克莱尼及埃米爾·波斯特（英语：Emil Post）的論文。在參考文獻中也會列出原作者的姓名。

参閱

•  计算机科学主题
•  计算机程序设计主题

• 抽象機器
• 算法作曲
• 高级综合
• 垃圾进，垃圾出
• 《算法导论》
• 计算理论
  • 可计算性理论
  • 計算複雜性理論

延伸阅读

[编]

  《欽定古今圖書集成·曆象彙編·曆法典·算法部》，出自陈梦雷《古今圖書集成》

外部链接

• 20世纪十大算法 （页面存档备份，存于互联网档案馆）
• 演算法笔记 （页面存档备份，存于互联网档案馆）
• 计算几何算法概览 （页面存档备份，存于互联网档案馆）