在数学和计算机科学中，算法是如何解决一类问题的明确规范。算法可以执行计算、数据处理、自动推理和其他任务。
作为一种有效的方法，算法可以在有限的空间和时间内用定义明确的形式语言[1] 来表示，以计算函数[2] [3] 。从初始状态和初始输入(可能为空)开始，[4] 指令描述了一种计算，当执行该计算时，该计算通过有限的[5] 数量的明确定义的连续状态，最终产生的“输出”[6] 并终止于最终结束状态。从一种状态到下一种状态的转变不一定是 明确的；一些被称为随机算法的算法包含随机输入。[7]
算法的概念已经存在了几个世纪。希腊数学家使用 Eratosthenes筛子中的算法寻找素数，欧几里德算法寻找两个数的最大公约数。
“算法”一词本身源自9世纪数学家muḥammad· ibn Mūsā al-Khwārizmī的拉丁化算法。后来成为现代算法概念的部分 规范化始于1928年 David Hilbert提出的解决判定问题 (决策问题)的尝试。后来的 规范化被 看作试图定义“有效可计算性”[8] 或“有效方法”。[9] 这些 规范化包括1930年、1934年和1935年的 Gödel–Herbrand–Kleene递归函数，1936年的 Alonzo Church的λ微积分，1936年的 Emil Post公式1，以及1936-37年和1939年 Alan Turing的图灵机。
“算法”一词起源于将 Muhammad ibn Musa al-Khwarizmi的名字拉丁化，这是 算法书的第一步。[10][11]Al-Khwārizmī(阿拉伯语:الخوارزمي，波斯语:خوارزمی，约780-850年)是巴格达智慧宫的波斯数学家、天文学家、地理学家和学者，他的名字的意思是“Khwarazm的本地人”， Khwarazm是大伊朗的一部分，现在在乌兹别克斯坦。[12][13]
大约在825年， al-Khwarizmi写了一篇关于印度-阿拉伯数字系统的阿拉伯语论文，该论文在12世纪被翻译成拉丁文，题目是《 Algoritmi de numero Indorum》。这个标题的意思是“印第安人数字上的 Algoritmi”，其中“ Algoritmi”是译者对 Al-Khwarizmi名字的拉丁化。[14]Al-Khwarizmi是中世纪晚期被 欧洲阅读最广泛的数学家，主要是通过他的另一本书《代数》。[15] 在中世纪晚期的拉丁语中，algorismus，英语中的“algorism”，都是他的名字的 传讹，仅仅意味着“十进制数字系统”。在15世纪，在希腊单词ἀριθμός“number”(参见“算术”)的影响下，拉丁语单词被改为algorithmus，相应的英语术语“algorithm”在17世纪首次得到证实；现代意义是在19世纪引入的。[16]
在英语中，它首先在1230年左右 被使用，然后在1391年被乔叟使用。英语采用了法语术语，但是直到19世纪末，“算法”才具有现代英语中的含义。
这个词的另一个早期用法是从1240年开始的，在 Alexandre de Villedieu撰写的一本名为《 Carmen de Algorismo》的手册中。它是这样开始的:
Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris.
其翻译为:
算法是一门通过现在我们使用印度数字的艺术， 数字是2乘以5。
这首诗有几百行长，总结了用印度骰子或印度数字的新风格计算的艺术。
有关“算法”定义的各种观点的详细介绍，请参见算法特性。[17] 非正式定义可以是“一组精确定义操作序列的规则”。[18]这将包括所有计算机程序，包括不执行数值计算的程序。一般来说，程序只有在最终停止时才是算法。[19]
算法的一个典型例子是欧几里德算法，用于确定两个整数的最大公约数；上面的流程图描述了一个示例(还有其他示例),并且在后面的部分中作为一个示例。
Boolos，Jeffrey & 1974，1999在下面的引文中给出了这个词的非正式含义:
没有人能写得足够快、足够长或足够小...（小得没有限度， 你会试图写在分子、原子、电子上)，通过用某种符号一个接一个地写出它们的名字来列出一个可列举的无限集合的所有成员。但是人类可以做一些同样有用的事情，在某些可列举的无限集合的情况下:对于任意有限的n，他们可以给出明确的指令来确定集合的第n个成员。这样的指令可以非常明确地给出，其形式是计算机或者只能对符号进行非常基本的运算的人可以 做到的。[20]
“可枚举无限集合”是指其元素可以与整数一一对应的集合。因此， Boolos和 Jeffrey说，一个算法意味着一个过程的指令，该过程从任意的“输入”整数或者理论上可以任意大的整数“创建”输出整数 。因此，一个算法可以是一个代数方程，比如y = m+n——两个任意的“输入变量”m和n，它们产生一个输出y。但是，不同作者对这个概念的定义表明，这个词隐含的意义远远不止于此，大约是(对于加法例子):
算法的概念也被用来定义可判定性的概念。这个概念对于解释 正式系统是如何从一小组公理和规则开始形成的至关重要。在逻辑上，一个算法完成所需的时间是无法测量的，因为它显然与我们习惯的物理维度无关。这种不确定性是正在进行的工作的特征，这种不确定性导致无法找到既适合具体(在某种意义上)又适合抽象术语使用的算法定义。
算法对计算机处理数据的方式至关重要。许多计算机程序都包含算法，这些算法详细说明了计算机执行特定任务(以特定顺序)应该执行的特定指令，例如计算员工工资或打印学生成绩单。因此，算法可以被认为是图灵完备系统可以模拟的任何操作序列。主张这一论点的作者包括 Minsky (1967)、 Savage (1987)和 Gurevich (2000):
Minsky:“但我们也会坚持，图灵...任何可以“自然地”被称为有效的程序，实际上可以通过(简单的)机器来实现。尽管这看起来有些极端，但争论...对它有利是很难反驳的”。[26]
Gurevich:"...图灵支持他论文的非正式论点证明了一个更强有力的论点:每种算法都可以由图灵机模拟...根据 Savage [1987)，算法是由图灵机定义的计算过程。[27]
通常，当算法与处理信息相关联时，数据可以从输入源读取，写入输出设备并存储以供进一步处理。存储的数据被视为执行算法的实体的内部状态的一部分。实际上，状态存储在一个或多个数据结构中。
对于一些这样的计算过程，算法必须被严格定义:在所有可能出现的情况下以其应用的方式指定。也就是说，任何有条件的步骤都必须系统地 逐一处理；每个案例的标准必须清晰(并且是可计算的)。
因为算法是精确步骤的精确列表，所以计算顺序对于算法的运行总是至关重要的。指令通常被认为是明确列出的，并且被描述为从“顶部”开始到“底部”，这种思想被更正式地描述为控制流。
到目前为止，关于算法形式化的讨论已经假定了命令式编程的前提。这是最常见的概念，它试图以离散的“机械”方式描述一项任务。这种形式化算法概念的独特之处在于赋值操作，它设置变量的值。它源于“记忆”作为便笺簿的直觉。下面有一个这样的例子。
关于算法构成的一些替代概念，请参见函数编程和逻辑编程。
算法可以用多种符号表示，包括自然语言、伪代码、流程图、drakon图表、编程语言或控制表(由解释器处理)。算法的自然语言表达往往冗长而模糊，很少用于复杂或技术性的算法。伪代码、流程图、drakon图表和控制表是表达算法的结构化方式，避免了自然语言语句中常见的许多歧义。编程语言主要用于以计算机可以执行的形式表达算法，但通常被用作定义或记录算法的一种方式。
有很多种可能的表示，可以将一个给定的图灵机程序表示为一系列的机器表(见有限状态机、状态转换表和控制表)，流程图和drakon图(见状态图)，或者表示为一种称为“四元组”的基本机器代码或汇编代码(见图灵机)。
算法的表示可以分为图灵机描述的三个公认的层次:[28]
算法设计是指解决问题和工程算法的方法或数学过程。算法设计是运筹学中许多求解理论的一部分，如动态规划和分治法。设计和实现算法设计的技术也被称为算法设计模式，[29] 例如模板方法模式和装饰模式。
算法设计的一个最重要的方面是创建一个具有高效运行时间的算法，也称为“大 O”
算法开发的典型步骤:
1.问题定义
2.模型的开发
3.算法说明
4.设计算法
5.检查算法的正确性
6.算法分析
7.算法的实现
8.程序测试
9.文件准备
在计算机系统中，算法基本上是软件开发人员用软件编写的逻辑实例， 使预定的“目标”计算机能够有效地从给定(可能为空)输入生成输出。一个最优算法，即使在旧硬件中运行，也会比在更高效的硬件中运行的非最优(时间复杂度更高)算法产生更快的结果；这就是为什么算法，像计算机硬件一样 ，被认为是技术的原因 。
“优雅”(紧凑)程序，“良好”(快速)程序:“简单和优雅”的概念非正式地产生 于 Knuth， 准确的产生于Chaitin:
Knuth:"...我们想要一些定义松散的美学意义上的好算法。一个标准...执行算法所花费的时间长度....其他标准是算法对计算机的适应性、简单性和优雅性等”[30]
Chaitin在他的定义前写道:“我会证明你不能证明一个程序是‘优雅的’”——这样的证明可以解决 停机问题(同上)。
算法与可由算法计算的函数:对于给定的函数，可能存在多种算法。这是真的，即使没有扩展程序员可用的指令集。 Rogers观察到“是的...区分算法概念(即过程)和可由算法计算的函数概念(即过程产生的映射)很重要。同一函数可能有几种不同的算法”。[32]
不幸的是，在好(速度)和优雅(紧凑)之间可能会有一个折衷——一个优雅的程序可能比一个不那么优雅的程序需要更多的步骤来完成一个计算。下面是一个使用欧几里德算法的例子。
计算机 ，计算模型:计算机(或人类“计算机”[33])是一种受限制的机器，一种盲目遵循指令的“离散确定性机械装置”[34] [35] Melzak和 Lambek的原始模型[36] 将这一概念简化为四个要素:(1)离散的、可区分的位置，(2)离散的、不可区分的计数器[37] (3)代理，以及(4)相对于代理能力有效的指令列表。[38]
Minsky在他的《可计算性的非常简单的基础》中描述了 Lambek的“算盘”模型的一个更相似的变体。[39] Minsky的机器通过它的五条(或六条，取决于如何计数)指令按顺序运行，除非有条件的“ IF–THEN GOTO”或无条件的“ GOTO”改变了程序的顺序。除了 停止， Minsky的机器还包括三个赋值(替换， 置换)[40] 操作:零(例如位置内容被0: L←0替换)、后继(例如 L← L+1)和递减(例如 L ← L − 1)。[41] 程序员很少用如此有限的指令集编写“代码”。但是 Minsky (像 Melzak和Lambek一样)表明，他的机器是只包括 四种通用类型的指令的图灵机:条件GOTO、无条件GOTO、赋值/替换/替换和 停止。然而，为了 图灵机完整性，还需要一些不同的赋值指令(例如， Minsky机器的减量、增量和零/清除/空指令)；他们的具体规格多少取决于 设计者。无条件的GOTO是一种便利；它可以通过将专用位置初始化为零来构建，例如指令“Z←0”；此后，指令如果Z=0，那么转到xxx是无条件的。
算法模拟:计算机 语言:Knuth建议读者，“学习算法的最好方法是尝试一下 ……立即拿起笔和纸，举一个例子”。[42] 但是真实事物的模拟或执行呢？程序员必须将算法翻译成模拟器/计算机 能够有效执行的语言。 Stone举了一个例子:当计算二次方程的根时，计算机必须知道如何求平方根。如果没有，那么算法要想有效，就必须提供一套提取平方根的规则。[43]
这意味着程序员必须知道一种相对于目标计算代理(计算机 )有效的“语言”。
但是模拟应该使用什么模型呢？ Van Emde Boas观察到，“即使我们把复杂性理论建立在抽象而不是具体的机器上，模型选择的任意性仍然存在。正是在这一点上，模拟的概念出现了”。[44] 当测量速度时，指令集很重要。例如，欧几里德算法中计算余数的子程序，如果程序员有一条“模数”指令可用，而不仅仅是减法(或者更糟的是，只有 Minsky的“减量”)，执行起来会快得多。
结构化编程，规范结构:根据 Church–Turing理论，任何算法都可以通过已知的图灵完全模型来计算，根据 Minsky的演示，图灵 完备只需要四种指令类型——条件GOTO，无条件GOTO，赋值， 停止。Kemeny和Kurtz观察到，虽然无条件GOTOs和有条件IF-THEN GOTOs的“无纪律”使用会导致“意大利面代码”，但程序员可以只使用这些指令编写结构化程序；另一方面，“用结构化语言编写结构不良的程序也是可能的，而且不会太难”。[45] Tausworthe增加了三个Böhm-Jacopini规范 结构:[46] 序列， IF-THEN-ELSE，和 WHILE-DO，还有两个: DO-WHILE和案例。[47] 结构化程序的另一个好处是它有助于用数学归纳法证明正确性。[48]
标准流程图符号[49]:称为流程图的图形助手，提供了一种描述和记录算法(和一个计算机程序)的方法。就像 Minsky机器的程序流程一样，流程图总是从页面的顶部开始向下进行。它的主要符号只有四个:显示程序流的有向箭头、矩形(序列、 GOTO)、菱形( IF-THEN-ELSE)和点( OR-tie)。 Böhm–Jacopini规范结构是由这些原始形状组成的。子结构可以“嵌套”在矩形中，但前提是上部结构只有一个出口。图中显示了这些符号及其用于构建规范结构的用途。
最简单的算法之一是在随机顺序的数字列表中找到最大的数字。找到解决方案需要查看列表中的每个数字。由此可以得出一个简单的算法，可以用英语散文的高级描述来表述:
高级描述:
(准)形式描述: 以下是更正式的伪代码语句编码或洋泾浜编码:
Algorithm LargestNumber 输入:数字列表 L²。 输出:列表中最大的数字 L²。
如果 l .尺寸 = 0返回null 最大的 ⅲ L²[0]
对于每一个 项目 在 L²，做
如果 项目 > 最大的那么 最大的 ⅲ 项目
返回 最大的
欧几里得计算两个数的最大公约数算法在他的第七卷《初等数论》中作为命题二出现 元素。[50] 欧几里得这样提出了这个问题:“给定两个互不质数，找到它们最大的公共测度”。他将“[数”定义为]由单位组成的群体:计数数，不包括零的正整数。“测量”是放置较短的测量长度 s 连续(q 时间)沿着更长的长度 l 直到剩余部分 r 小于较短的长度 s。[51] 用现代话说，余数 r = l − q×s, q 是商，或余数 r 是“模数”，除法之后剩下的整数分数部分。[52]
欧几里得方法要成功，起始长度必须满足两个要求:(1)长度不能为零，(2)减法必须“正确”；也就是说，一个测试必须保证两个数字中较小的那个被从较大的那个中减去(或者，两个可以相等，所以它们的相减得到零)。
欧几里得的原始证明增加了第三个要求:两个长度不能互相质数。欧几里得这样规定是为了构造一个归谬反证法证明，证明两个数的共同测度实际上是 最好的。[53] 虽然尼科马库斯算法与欧几里得算法相同，但当这些数互为质数时，它们的公共测度会得到数“1”。所以，准确地说，下面是真正的尼科马库斯算法。
欧几里得算法的计算机语言
只有几条指令 类型 需要执行欧几里得算法——一些逻辑测试(条件GOTO)、无条件GOTO、赋值(替换)和减法。
欧几里得算法的一个不雅程序
下面的算法被构造成克努特的欧几里得和尼科马库斯的四步版本，但是它没有使用除法来寻找余数，而是使用较短长度的连续减法 s 从剩余长度 r 直到 r 小于 s。粗体显示的高级描述改编自克努特1973:2–4:
输入:
1 [分成两个位置，L和S把数字 l 和 s 代表两个长度]: 输入L，S 2 [初始化R:剩下的长度 r 等于起始/初始/输入长度 l]: R ← L
E0:[确保 r ≥ s。]
3 [确保两个数字中较小的在S中，较大的在R中]:
如果R > S，则
L的内容是更大的数字，所以略过交换-步骤4，5和6:
转到步骤6
其他
交换R和s的内容。
4 L ← R(第一步是多余的，但对后面的讨论很有用)。
5 R ← S
6 S ← LE1:[找到余数]:直到剩余长度 r 在R小于较短的长度 s 在S中，重复减去测量数 s 剩余长度的S r 在r区
7 如果S > R，则
完成测量
GOTO 10
其他
再次测量，
8 R←R-S
9 [余数循环]:
GOTO 7。E2:[余数为零吗？]:要么(I)最后一个度量是精确的，R中的余数为零，程序可以停止，要么(ii)算法必须继续:最后一个度量在R中留下的余数小于s中的度量数。
10 如果R = 0，则
这样做
转到步骤15
其他
继续到步骤11，E3:[互通 s 和 r]:欧几里得算法的难点。使用余数 r 来测量以前较小的数字 s；我只是一个临时位置。
11 L ← R
12 R ← S
13 S ← L
14 [重复测量过程]:
GOTO 7输出:
15 [完成。s包含最大公约数]: 打印
完成:
16 停止，结束，停止。
欧几里得算法的优美程序
The following version of Euclid's algorithm requires only six core instructions to do what thirteen are required to do by "Inelegant"; worse, "Inelegant" requires more types of instructions.[需要解释] “优雅”的流程图可以在本文的顶部找到。在(非结构化)基础语言中，步骤被编号，指令 LET [] = [] 是用←符号表示的赋值指令。
5 REM Euclid's algorithm for greatest common divisor
6 PRINT "Type two integers greater than 0"
10 INPUT A,B
20 IF B=0 THEN GOTO 80
30 IF A > B THEN GOTO 60
40 LET B=B-A
50 GOTO 20
60 LET A=A-B
70 GOTO 20
80 PRINT A
90 END“优雅”是如何运作的:代替外部的“欧几里得环”，“优雅”在两个“共环”之间来回移动，A > B环计算A←A-B，B ≤ A环计算B←B-A。 s (新的测量长度)和减数可以成为新的 r (要测量的长度)；换句话说，减法的“意义”颠倒了。
以下版本可用于面向对象语言:
// Euclid's algorithm for greatest common divisor
int euclidAlgorithm (int A, int B){
A=Math.abs(A);
B=Math.abs(B);
while (B!=0){
if (A>B) A=A-B;
else B=B-A;
}
return A;
}一个算法做了作者希望它做的事情吗？一些测试用例通常会给核心功能带来一些信心。但是测试是不够的。对于测试用例，一个来源[54] 使用3009和884。克努特建议40902，24140。另一个有趣的例子是两个互质数字14157和5950。
但是“例外情况”[55] 必须被识别和测试。当R > S，S > R，R = S时，“不优雅”会正常运行吗？“优雅”也是如此:B > A，A > B，A = B？(对所有人都是)。当一个数为零，两个数都为零时会发生什么？(“不雅”在所有情况下永远计算；当A = 0时，“优雅”将永远计算。)如果 否定 输入了数字？分数？如果输入数字，即由算法/程序计算的函数的域，只包括包括零的正整数，那么零的故障表明算法(以及实例化它的程序)是一个部分函数而不是一个总函数。一个值得注意的例外是阿丽亚娜5号飞行501火箭故障(1996年6月4日)。
用数学归纳法证明程序的正确性:Knuth演示了数学归纳法在欧几里得算法“扩展”版本中的应用，并提出了“一种适用于证明任何算法有效性的通用方法”。[56] 陶斯沃特提出，一个程序复杂性的度量标准是其正确性证明的长度。[57]
优雅(紧凑)与善良(速度):只有六个核心指令，“优雅”是明显的赢家，相比之下，“不雅”是十三个指令。然而，“不雅”是 更快的 (它以更少的步骤到达HALT)。算法分析[58] 指出为什么会是这种情况:“优雅”确实如此 二 每个减法循环中的条件测试，而“不合格”只做一个。由于算法(通常)需要多次循环， 平均 做“B = 0”会浪费很多时间仅在计算完余数后才需要的测试。
算法可以改进吗？:一旦程序员判断一个程序“合适”和“有效”——也就是说，它计算出作者想要的函数——那么问题就变成了，它能被改进吗？
“不雅”的紧凑性可以通过消除五个步骤来提高。但是柴丁证明了压缩算法不能由广义算法自动完成；[59] 相反，它只能启发式地完成；即通过详尽的搜索(例如在《忙碌的海狸》中找到的例子)、反复试验、聪明、洞察力、归纳推理的应用等。观察步骤4、5和6在步骤11、12和13中重复。与“优雅”的比较暗示了这些步骤以及步骤2和3可以被取消。这将核心指令的数量从十三个减少到八个，这使得它在九个步骤中比“优雅”更“优雅”。
移动“B=0”可以提高“优雅”的速度在两个减法循环之外进行测试。这种变化需要增加三条指令(B = 0？，A = 0？，GOTO)。现在“优雅”计算示例数的速度更快；对于任何给定的A、B和R、S是否总是这种情况，需要详细的分析。
知道给定算法理论上需要多少特定资源(例如时间或存储)通常很重要。已经开发了用于分析算法以获得这种定量答案(估计)的方法；例如，上面的排序算法有一个时间要求为 O(n)，使用大 O符号，n作为列表的长度。在任何时候，算法只需要记住两个值:迄今为止找到的最大数字，以及它在输入列表中的当前位置。因此，如果不计算存储输入数字所需的空间，则称其空间要求为 O(1)，如果计算了，则称其为O (n)。
与其他算法相比，不同的算法可以用不同的指令集在更少或更多的时间、空间或“努力程度 ”内完成相同的任务。例如，当用于排序列表或数组上的表查找时，二进制搜索算法( 时间复杂度为 O(log n))优于顺序搜索( 时间复杂度为O (n))。
算法的分析和研究是计算机科学的一门学科，通常在不使用特定编程语言或实现的情况下进行抽象实践。在这个意义上，算法分析类似于其他数学学科，因为它关注算法的基本属性，而不是任何特定实现的细节。伪代码通常用于分析，因为它是最简单和最通用的表示。然而，最终，大多数算法通常在特定的硬件/软件平台上实现，并且它们的算法效率最终使用真实代码进行测试。对于“一次性”问题的解决，特定算法的效率可能不会产生重大影响(除非n非常大)，但对于为快速交互、商业或长寿命科学应用而设计的算法来说，这可能是至关重要的。从小n到大n的缩放经常暴露出 效率低下的算法，而这些算法在其他方面是优良的。
经验测试很有用，因为它可能会发现影响性能的意外交互。基准可以用来比较程序优化后算法的潜在改进前后效率提高 。然而，经验测试不能取代形式分析，以 直接的方式进行也不是小事。[60]
为了说明即使在成熟的算法中也可能有潜在的改进，与快速傅立叶变换算法(在图像处理领域中大量使用)相关的最近一项重大创新可以将医学成像等应用的处理时间减少 高达1000倍。[61] 一般来说，速度的提高取决于问题的特殊性质，这在实际应用中非常常见。[62] 如此大规模的加速使得 大量使用图像处理的计算设备(如数码相机和医疗设备)消耗更少的能量。
有多种方法对算法进行分类，每种方法都有自己的优点。
算法分类的一种方法是通过实现方式。
|
| Recursive C implementation of Euclid's algorithm from the above flowchart |
算法分类的另一种方法是通过它们的设计方法或范例。有一定数量的范例，每一个都不同。此外，这些类别中的每一个都包括许多不同类型的算法。一些常见的范例是:
对于优化问题，有更具体的算法分类；这种问题的算法可以属于上述一个或多个一般类别，也可以属于以下类别之一:
每个科学领域都有自己的问题，需要高效的算法。一个领域的相关问题经常一起研究。一些示例类是搜索算法、排序算法、 归并算法、数值算法、图形算法、字符串算法、计算几何算法、组合算法、医学算法、机器学习、密码学、数据压缩算法和解析技术。
领域往往相互重叠，一个 领域的算法进步可能会改善其他 领域的算法进步，有时这些 领域完全不相关。例如，动态规划是为了优化工业中的资源消耗而发明的，但现在被用于解决许多领域的 一大系列问题。
算法可以根据完成所需的时间和输入大小进行分类:
一些问题可能有不同复杂性的多种算法，而其他问题可能没有算法或没有已知的有效算法。也有从一些问题到其他问题的映射。因此， 结果表明，基于最优算法的复杂度，将问题本身分类，而不是将算法划分为等价类更合适。
形容词“连续”在应用于“算法”一词时可以表示:
算法本身通常不具备专利性。在美国，仅由抽象概念、数字或信号的简单操作组成的权利要求不构成“过程”(USPTO 2006)，因此算法不可申请专利(如 Gottschalk v. Benson案)。然而算法的实际应用有时是可以申请专利的。例如，在 Diamond v. Diehr案中，应用简单的反馈算法来帮助合成橡胶固化被认为是可申请 专利的。软件专利极具争议性，而且有很多备受批评的专利涉及算法，尤其是数据压缩算法，如 Unisys的LZW专利。
此外，一些加密算法有导出限制(请参见加密导出)。
算法在古希腊被使用。两个例子是 Eratosthenes的筛子，在[ Nicomachus的《算术导论》中有所描述，[68][69] 第9.2章，欧几里德算法，在欧几里德的《元素》(公元前300年)中首次有所描述。[69] 巴比伦 泥板文书描述并使用算法程序来计算重大天文事件的时间和地点。[69]
计数标记:为了记录他们的羊群，他们的粮食袋和他们的钱，古人使用计数法:积累石头或在棍子上划的标记，或者用粘土制作离散的符号。通过巴比伦人和埃及人 对标记和符号的使用，最终罗马数字和算盘得到了发展( Dilson，第16-41页)。计数标记在图灵机和后图灵机计算中使用的一元数字系统算法中表现突出。
古希腊几何学家(欧几里得算法)、印度数学家 Brahmagupta和波斯数学家 Al-Khwarizmi (术语“ 十进位计算法”和“算法”是从他 的名字中派生出来的)以及西欧数学家的工作使在莱布尼茨的微积分推理器概念(约1680年)中达到了顶峰 :
早于他所处时代整整一个半世纪 ，莱布尼茨提出了一 种逻辑代数，这 种代数将像普通代数规定操纵数字的规则一样规定操纵逻辑概念的规则.[70]
时钟: Bolter将重量驱动时钟的发明 誉为“中世纪欧洲的关键发明”，特别是边缘擒纵机构[71] 它为我们提供了机械钟的滴答声。“精确的自动机器”[72] 从13世纪开始，立即 催生了“机械自动机”，最终 催生了“计算机器”——19世纪中期 Charles Babbage和 Ada Lovelace伯爵夫人的差分机和分析机 。[73] Lovelace被认为是第一个设计用于计算机处理的算法的人—— Babbage的分析机 ， 被认为是第一个真正的图灵完整的计算机而不仅仅是计算器——因此Lovelace 有时被称为“历史上的第一个程序员”，尽管 Babbage的第二个设备的完整实现要等到她死后几十年才能实现。
逻辑机器1870年—— Stanley Jevons的“逻辑算盘”和“逻辑机器”:技术问题是当布尔方程以类似于现在被称为卡诺图的形式出现时，要简化布尔方程。 Jevons (1880)首先描述了一个简单的“算盘”，由“木条”组成，木条上有 指针，指针被 设计成可以机械地挑选出逻辑组合的任何部分或类别...然而，最近，我把系统简化为一种完全机械的形式，并因此把整个间接推理过程具体化为所谓的逻辑机器。他的机器配备了“某些可移动的木棒”和“脚下有21个键，像钢琴等的键一样……”。有了这台机器，他可以分析“三段论或任何其他简单的逻辑论证”。[74]
1870年，他在皇家学会的研究员面前展示了这台机器。[75] 然而，另一位逻辑学家 John Venn在他1881年的《符号逻辑》中对这一努力持偏见:“我对有时被称为逻辑机器的兴趣或重要性没有很高的 评价...在我看来，目前已知或可能被发现的任何发明都不值得被称为逻辑机器”； 到算法特性中查看更多。但他也不甘示弱，提出了“一个有点类似于 Jevon教授算盘的计划... 又一次，对应于 Jevons教授的逻辑机器，以下发明可以描述。我更喜欢称它为逻辑图机器...但我认为它可以完全做到任何逻辑机器合理预期的一切”。[76]
提花织机、 Hollerith穿孔卡、电报和电话——机电继电器: Bell和 Newell (1971年)指出，提花织机(1801年)、 Hollerith卡的前身 (穿孔卡，1887年)和“电话交换技术”是导致第一批计算机发展的根源。[77] 到19世纪中叶，电话的前身电报已经在全世界使用，它对字母的离散和可区分的编码是“点和破折号”，这是一种常见的声音。到了19世纪末， 自动收报机纸条(约19世纪70年代)开始使用，就像1890年美国人口普查中Hollerith 卡的使用一样。然后是电传打字机( 大约在1910年)，在 打孔纸上使用 Baudot码。
机电继电器的电话交换网络(发明于1835年)是以数字加法设备的发明者 George Stibitz (1937年) 的工作为基础的。当他在贝尔实验室工作时，他观察到机械计算器和齿轮的“累赘”使用。“1937年的一个晚上，他回到家，打算验证他的想法...修补工作结束后， Stibitz建造了一个二进制加法装置”。[78]
Davis (2000)观察到机电继电器的特殊重要性(其两个“二进制状态”打开和关闭):
符号和规则:接连不断地， George Boole (1847，1854)、 Gottlob Frege (1879)和 Giuseppe Peano (1888-1889)的数学运算 将算术简化为由规则操纵的符号序列。 Peano的《算术原理》，由一种新方法(1888年)提出，是“用符号语言对数学进行公理化的第一次尝试”。[80]
但是 Heijenoort给了Frege (1879)这样的 赞誉: Frege 的作品“也许是逻辑史上最重要的一部作品。...其中我们看到了一种“公式语言”，这是一种语言特征，一种用特殊符号写成的语言，“用于纯粹的思考”，也就是说，没有修辞修饰...由根据明确规则操纵的特定符号构成”。[81]Frege 的工作被 Alfred North Whitehead和 Bertrand Russell在其《数学原理》(1910-1913)中进一步简化和 扩充。
悖论:与此同时，一些令人不安的悖论出现在 著作中，特别是 Burali-Forti悖论(1897)、 Russell悖论(1902-03)和 Richard悖论。[82] 由此产生的考虑导致 Kurt Gödel的论文(1931年)——他特别引用了说谎者的悖论——将递归规则完全简化为数字。
有效计算能力:为了解决 Hilbert在1928年精确定义的判定问题 ，数学家们首先开始定义“有效方法”或“有效计算”或“有效计算能力”的含义(即，一个会成功的计算)。接下来，Alonzo Church、Stephen Kleene和J.B. Rosser 的λ演算[83] 根据 Gödel的工作，按照 Jacques Herbrand的建议(参见 Gödel1934年的普林斯顿讲座)和 Kleene后来的简化，对“一般递归”进行了精细的定义。[84] Church的证明是[85] 判定问题 是不可解决的， Emil Post对有效计算能力的定义是，一个工人盲目地遵循一系列指令，在一系列房间里向左或向右移动，在那里或者标记或擦除一张纸，或者观察这张纸，然后对下一条指令做出是或否的决定。[86] Alan Turing用他的“a-[自动-]机器[87]证明判定 问题是无法解决的——实际上几乎与 Post的“公式”相同，J. Barkley Rosser用“机器”来定义“有效方法”。[88] S.C. Kleene提出的“ Church论文”的前身，他称之为“论文一”，[89] 几年后 Kleene重命名他的论文为“Church 的论文”[90] 和提出“ Turing的论文”。[91]
Emil Post (1936)对“计算机”(人类)的行为描述如下:
Alan Turing的作品[93] 早于 Stibitz的作品(1937)；还不知道 Stibitz是否知道 Turing的工作。 Turing的传记作者认为图灵 Turing使用打字机一样的模型源于 小时候的兴趣:“艾伦小时候就梦想发明打字机；图灵夫人有一台打字机，他 可能是从问自己把打字机叫做‘机械’是什么意思开始的。[94] 鉴于莫尔斯电码和电报、自动收报机和电传打字机的普及，我们[是谁？]可能猜想所有这些都是影响。
Turing——他的计算模型现在被称为图灵机——和 Post一样，开始于对人类计算机的分析，他把分析简化为一组简单的基本运动和“ 思维状态”。但是他更进一步，创造了一台机器作为计算数字的模型。[95]
Turing的归约产生了以下结果:
“因此，简单的操作必须包括:
"(a)观察到的一个方块上的符号发生变化
"(b)观察到的一个正方形向先前观察到的一个正方形的L个正方形内的另一个正方形的变化。
“可能其中一些变化必然会引起 思维状态的变化。因此，最一般的单一操作必须被视为以下操作之一:
"(A) 符号的可能变化以及 思维状态的可能变化。
(B) 观察到的正方形的可能变化，以及思维状态 的可能变化
"我们现在可以建造一台机器来完成这台计算机的工作."[96]
几年后，图灵用这种有力的表达扩展了他的分析(论文，定义):
如果一个函数的值可以通过一些纯粹的机械过程找到，那么这个函数就被称为是“可有效计算的”。尽管很容易直观地理解这一概念，但还是希望有一些更明确的、数学上可表达的定义...[:他讨论了定义的历史，就像上面提到的 Gödel, Herbrand, Kleene, Church, Turing, and Post一样]...我们可以从字面上理解这句话，理解为一个可以被机器执行纯粹的机械过程 。有可能以某种形式给出这些机器结构的数学描述。这些思想的发展 引出了作者对可计算函数的定义，以及对可有效计算的可计算性 的识别...。
“我们将使用表达式“可计算函数”来表示可由机器计算的函数，并且我们让“可有效计算的”指的是直观的概念，而不与这些定义中的任何一个进行特殊的标识”。[97]
J. Barkley Rosser以下列方式定义了“有效的[数学]方法”(增加了斜体):
“‘有效方法’在这里是以一种意义相当特殊的方法 来使用的，该方法的每一个步骤都被精确地确定，并且肯定会在有限的步骤中产生答案。有了这种特殊的含义，迄今为止已经给出了三种不同的精确定义。[，他的脚注5；请参见下面的讨论]。其中最简单的陈述( 归功于Post和Turing)说，如果一个人能造出一台机器来解决这组问题，除了插入问题和(稍后)阅读答案之外，不需要任何人的干预，就能解决这组问题，那么这就是解决某些问题的有效方法。这三个定义都是等价的，所以使用哪一个并不重要。此外，这三者都是等价的这一事实是任何一种方法 正确性的有力论据。”( Rosser 1939:225–226)
Rosser的脚注5提到了(1)Church和Kleene 的工作以及他们对λ可定义性的定义，特别是 Church在他的《初等数论的一个无法解决的问题》(1936)中对λ可定义性的使用；(2) Herbrand和 Gödel及其递归的使用，特别是 Gödel在他的著名论文《数学原理及相关系统的形式不可判定命题一》(1931)中的使用；和(3)Post(1936)和Turing (1936-37)在他们的计算机制模型中。
Stephen C. Kleene把他现在著名的“论文一”定义为 Church—— Turing论文。但他是在以下背景下这样做的(原文为黑体):
“12。算法理论...在建立一个完整的算法理论的过程中，我们所做的是描述一个过程，这个过程对于独立变量的每一组值都是可执行的，这个过程必须终止，并且以这样的方式，从结果中我们可以读到一个明确的答案，“是”或“否”，对于这个问题，“这个断言的值 是真的吗？" "( Kleene1943:273)
为了进一步完善“算法”的定义 ，人们付出了大量的努力。由于围绕数学基础(尤其是Church -Turing 论文)和 精神哲学(尤其是关于人工智能的争论)的问题，活动仍在继续。有关更多信息，请参见算法特性。
^"Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987: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)..
^"an algorithm is a procedure for computing a function (with respect to some chosen notation for integers) ... this limitation (to numerical functions) results in no loss of generality", (Rogers 1987:1)..
^"An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins" (Knuth 1973: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)..
^"An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs" (Knuth 1973:5)..
^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 the use of continuous methods or analogue devices ... carried forward deterministically, without resort to random methods or devices, e.g., dice" (Rogers 1987:2)..
^Kleene 1943 in Davis 1965:274.
^Rosser 1939 in Davis 1965:225.
^"Al-Khwarizmi biography". www-history.mcs.st-andrews.ac.uk..
^"Etymology of algorithm". Chambers Dictionary. Retrieved December 13, 2016..
^Hogendijk, Jan P. (1998). "al-Khwarzimi". Pythagoras. 38 (2): 4–5. Archived from the original on April 12, 2009..
^Oaks, Jeffrey A. "Was al-Khwarizmi an applied algebraist?". University of Indianapolis. Archived from the original on November 15, 2010. Retrieved May 30, 2008..
^Brezina, Corona (2006). Al-Khwarizmi: The Inventor Of Algebra. The Rosen Publishing Group. ISBN 978-1-4042-0513-0..
^Foremost mathematical texts in history, according to Carl B. Boyer..
^Oxford English Dictionary, Third Edition, 2012 s.v..
^Stone 1973:4.
^Simanowski, Roberto (2018). The Death Algorithm and Other Digital Dilemmas. Untimely Meditations. 14. Translated by Chase, Jefferson. Cambridge, Massachusetts: MIT Press. p. 147. ISBN 9780262536370. Retrieved 27 May 2019. [...] the next level of abstraction of central bureaucracy: globally operating algorithms..
^Stone simply requires that "it must terminate in a finite number of steps" (Stone 1973:7–8)..
^Boolos and Jeffrey 1974,1999:19.
^cf Stone 1972:5.
^Knuth 1973:7 states: "In practice we not only want algorithms, we want good algorithms ... one criterion of goodness is the length of time taken to perform the algorithm ... other criteria are the adaptability of the algorithm to computers, its simplicity, and elegance, etc.".
^cf Stone 1973:6.
^Stone 1973:7–8 states that there must be, "...a procedure that a robot [i.e., computer] can follow in order to determine precisely how to obey the instruction". Stone adds finiteness of the process, and definiteness (having no ambiguity in the instructions) to this definition..
^Knuth, loc. cit.
^Minsky 1967.
^Gurevich 2000:1, 3.
^Sipser 2006:157.
^Goodrich, Michael T.; Tamassia, Roberto (2002), Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons, Inc., ISBN 978-0-471-38365-9.
^Knuth 1973:7.
^Chaitin 2005:32.
^Rogers 1987:1–2.
^In his essay "Calculations by Man and Machine: Conceptual Analysis" Seig 2002:390 credits this distinction to Robin Gandy, cf Wilfred Seig, et al., 2002 Reflections on the foundations of mathematics: Essays in honor of Solomon Feferman, Association for Symbolic Logic, A.K. Peters Ltd, Natick, MA..
^cf Gandy 1980:126, Robin Gandy Church's Thesis and Principles for Mechanisms appearing on pp. 123–148 in J. Barwise et al. 1980 The Kleene Symposium, North-Holland Publishing Company..
^A "robot": "A computer is a robot that performs any task that can be described as a sequence of instructions." cf Stone 1972:3.
^Lambek's "abacus" is a "countably infinite number of locations (holes, wires etc.) together with an unlimited supply of counters (pebbles, beads, etc). The locations are distinguishable, the counters are not". The holes have unlimited capacity, and standing by is an agent who understands and is able to carry out the list of instructions" (Lambek 1961:295). Lambek references Melzak who defines his Q-machine as "an indefinitely large number of locations ... an indefinitely large supply of counters distributed among these locations, a program, and an operator whose sole purpose is to carry out the program" (Melzak 1961:283). B-B-J (loc. cit.) add the stipulation that the holes are "capable of holding any number of stones" (p. 46). Both Melzak and Lambek appear in The Canadian Mathematical Bulletin, vol. 4, no. 3, September 1961..
^If no confusion results, the word "counters" can be dropped, and a location can be said to contain a single "number"..
^"We say that an instruction is effective if there is a procedure that the robot can follow in order to determine precisely how to obey the instruction." (Stone 1972:6).
^cf Minsky 1967: Chapter 11 "Computer models" and Chapter 14 "Very Simple Bases for Computability" pp. 255–281 in particular.
^cf Knuth 1973:3..
^But always preceded by IF–THEN to avoid improper subtraction..
^Knuth 1973:4.
^Stone 1972:5. Methods for extracting roots are not trivial: see Methods of computing square roots..
^Leeuwen, Jan (1990). Handbook of Theoretical Computer Science: Algorithms and complexity. Volume A. Elsevier. p. 85. ISBN 978-0-444-88071-0..
^John G. Kemeny and Thomas E. Kurtz 1985 Back to Basic: The History, Corruption, and Future of the Language, Addison-Wesley Publishing Company, Inc. Reading, MA, ISBN 0-201-13433-0..
^Tausworthe 1977:101.
^Tausworthe 1977:142.
^Knuth 1973 section 1.2.1, expanded by Tausworthe 1977 at pages 100ff and Chapter 9.1.
^cf Tausworthe 1977.
^Heath 1908:300; Hawking's Dover 2005 edition derives from Heath..
^" 'Let CD, measuring BF, leave FA less than itself.' This is a neat abbreviation for saying, measure along BA successive lengths equal to CD until a point F is reached such that the length FA remaining is less than CD; in other words, let BF be the largest exact multiple of CD contained in BA" (Heath 1908:297).
^For modern treatments using division in the algorithm, see Hardy and Wright 1979:180, Knuth 1973:2 (Volume 1), plus more discussion of Euclid's algorithm in Knuth 1969:293–297 (Volume 2)..
^Euclid covers this question in his Proposition 1..
^"Euclid's Elements, Book VII, Proposition 2". Aleph0.clarku.edu. Retrieved May 20, 2012..
^While this notion is in widespread use, it cannot be defined precisely..
^Knuth 1973:13–18. He credits "the formulation of algorithm-proving in terms of assertions and induction" to R W. Floyd, Peter Naur, C.A.R. Hoare, H.H. Goldstine and J. von Neumann. Tausworth 1977 borrows Knuth's Euclid example and extends Knuth's method in section 9.1 Formal Proofs (pp. 288–298)..
^Tausworthe 1997:294.
^cf Knuth 1973:7 (Vol. I), and his more-detailed analyses on pp. 1969:294–313 (Vol II)..
^Breakdown occurs when an algorithm tries to compact itself. Success would solve the Halting problem..
^Kriegel, Hans-Peter; Schubert, Erich; Zimek, Arthur (2016). "The (black) art of run-time evaluation: Are we comparing algorithms or implementations?". Knowledge and Information Systems. 52 (2): 341–378. doi:10.1007/s10115-016-1004-2. ISSN 0219-1377..
^Gillian Conahan (January 2013). "Better Math Makes Faster Data Networks". discovermagazine.com..
^Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price, "ACM-SIAM Symposium On Discrete Algorithms (SODA) Archived 7月 4, 2013 at the Wayback Machine, Kyoto, January 2012. See also the sFFT Web Page..
^Kowalski 1979.
^Knapsack Problems | Hans Kellerer | Springer (in 英语). Springer. 2004. ISBN 978-3-540-40286-2..
^Carroll, Sue; Daughtrey, Taz (July 4, 2007). Fundamental Concepts for the Software Quality Engineer. American Society for Quality. pp. 282 et seq. ISBN 978-0-87389-720-4..
^George B. Dantzig and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag..
^Tsypkin (1971). Adaptation and learning in automatic systems. Academic Press. p. 54. ISBN 978-0-08-095582-7..
^Ast, Courtney. "Eratosthenes". Wichita State University: Department of Mathematics and Statistics..
^Cooke, Roger L. (2005). The History of Mathematics: A Brief Course. John Wiley & Sons. ISBN 978-1-118-46029-0..
^Davis 2000:18.
^Bolter 1984:24.
^Bolter 1984:26.
^Bolter 1984:33–34, 204–206..
^All quotes from W. Stanley Jevons 1880 Elementary Lessons in Logic: Deductive and Inductive, Macmillan and Co., London and New York. Republished as a googlebook; cf Jevons 1880:199–201. Louis Couturat 1914 the Algebra of Logic, The Open Court Publishing Company, Chicago and London. Republished as a googlebook; cf Couturat 1914:75–76 gives a few more details; he compares this to a typewriter as well as a piano. Jevons states that the account is to be found at January 20, 1870 The Proceedings of the Royal Society..
^Jevons 1880:199–200.
^All quotes from John Venn 1881 Symbolic Logic, Macmillan and Co., London. Republished as a googlebook. cf Venn 1881:120–125. The interested reader can find a deeper explanation in those pages..
^Bell and Newell diagram 1971:39, cf. Davis 2000.
^* Melina Hill, Valley News Correspondent, A Tinkerer Gets a Place in History, Valley News West Lebanon NH, Thursday, March 31, 1983, p. 13..
^Davis 2000:14.
^van Heijenoort 1967:81ff.
^van Heijenoort's commentary on Frege's Begriffsschrift, a formula language, modeled upon that of arithmetic, for pure thought in van Heijenoort 1967:1.
^Dixon 1906, cf. Kleene 1952:36–40.
^cf. footnote in Alonzo Church 1936a in Davis 1965:90 and 1936b in Davis 1965:110.
^Kleene 1935–6 in Davis 1965:237ff, Kleene 1943 in Davis 1965:255ff.
^Church 1936 in Davis 1965:88ff.
^cf. "Finite Combinatory Processes – formulation 1", Post 1936 in Davis 1965:289–290.
^Turing 1936–37 in Davis 1965:116ff.
^Rosser 1939 in Davis 1965:226.
^Kleene 1943 in Davis 1965:273–274.
^Kleene 1952:300, 317.
^Kleene 1952:376.
^Turing 1936–37 in Davis 1965:289–290.
^Turing 1936 in Davis 1965, Turing 1939 in Davis 1965:160.
^Hodges, p. 96.
^Turing 1936–37:116.
^Turing 1936–37 in Davis 1965:136.
^Turing 1939 in Davis 1965:160.
暂无