算法

在数学和计算机科学中，算法（Algorithm）是如何解决一类问题的明确规范。 算法可以执行计算，数据处理和自动推理任务。

作为一种有效的方法，算法可以在有限的空间和时间内以及用于计算函数的明确定义的形式语言来表达。 从初始状态和初始输入（可能为空）开始，指令描述了一个计算，该计算在执行时通过有限数量的明确的连续状态进行，最终产生“输出”并终止于最终结束状态。 从一个州到另一个州的过渡不一定是确定性的; 一些称为随机算法的算法结合了随机输入。

算法的概念已经存在了几个世纪，这个概念的使用可以归因于希腊数学家，例如Eratosthenes和Euclid算法的筛选; 术语算法本身来自9世纪数学家MuḥammadibnMūsāal’Khwārizmī，拉丁语’Algoritmi’。 将成为现代算法概念的部分形式化始于试图解决David Hilbert于1928年提出的Entscheidungs问题（“决策问题”）。随后的形式化被定义为试图定义“有效可计算性”或“有效方法” ; 这些形式化包括1930,1934和1935年的Gödel-Herbrand-Kleene递归函数，1936年的Alonzo Church的lambda微积分，1936年的Emil Post的Formulation 1，以及1936-7和1939年的Alan Turing的图灵机。

词源
‘算法’这个词的根源在于将穆罕默德·伊本·穆萨·赫瓦兹米的名字拉到算法的第一步。 Al-Khwārizmī（波斯语：خوارزمی，约780-850年）是巴格达智慧之家的波斯数学家，天文学家，地理学家和学者，他的名字的意思是“Khwarezm的原住民”，该地区属于大伊朗，现在在乌兹别克斯坦。

大约在825年，赫尔瓦兹米写了关于印度 – 阿拉伯数字系统的阿拉伯语言论文，该论文在12世纪被翻译成拉丁语，标题是Algoritmi de numero Indorum。 这个标题的意思是“Algoritmi关于印第安人的数量”，其中“Algoritmi”是译者对Al-Khwarizmi的名字的拉丁化。 Al Khwarizmi是中世纪后期欧洲最广泛阅读的数学家，主要是通过他的另一本着作“代数”。 在中世纪后期的拉丁语中，algorismus，英文“algorism”，他的名字的腐败，只是意味着“十进制数字系统”。 在十五世纪，受希腊词ἀριθμός’数字’（参见’算术’）的影响，拉丁词改为算法，相应的英语词’算法’首先在17世纪被证实; 现代意义是在19世纪引入的。

在英语中，它大约在1230年首次被使用，然后在1391年被乔in使用。英语采用了法语术语，但直到19世纪后期，“算法”才具有现代英语的意义。

这个词的另一个早期使用是从1240年，在一个由Alexandre de Villedieu组成的名为Carmen de Algorismo的手册中。 它因此开始：

Haec algorismus ars praesens dicitur，qua / Talibus Indorum fruimur bis quinque figuris。

其翻译为：

算术是目前我们使用那些数量是五倍的印度人物的艺术。

这首诗长达几百行，总结了用印度骰子或塔利布斯印度人或印度教数字计算新艺术的艺术。

非正式的定义
有关“算法”定义的各种观点的详细介绍，请参阅算法特征描述。
一个非正式的定义可能是“一组精确定义一系列操作的规则。” 其中将包括所有计算机程序，包括不执行数字计算的程序。 一般来说，如果程序最终停止，程序只是一种算法。

算法的典型例子是用于确定两个整数的最大公约数的欧几里得算法; 上面的流程图描述了一个示例（还有其他示例），并在后面的章节中作为示例。

Boolos，Jeffrey＆1974,1999在下面的引文中提供了这个词的非正式含义：

没有人能写得足够快，或者足够长，或者足够小（†“越来越小，没有限制……你会试图在分子，原子和电子上写字）”，列出所有的成员无数次地通过用一些符号一个接一个地写出他们的名字来形容。 但是，对于某些无限集合，人类可以做同样有用的事情：对于任意有限n，他们可以给出确定集合的第n个成员的明确指示。 这样的指令应该以一种计算机器可以遵循的形式或者只能对符号进行非常基本操作的人的形式给出。

一个“无限集合”是指其元素可以与整数一一对应的元素。 因此，Boolos和Jeffrey在说，一种算法意味着一个过程的指令，该过程可以从任意“输入”整数或“整数”“创造”输出整数，理论上，整数可以是任意大的。 因此，算法可以是代数方程，例如y = m + n – 产生输出y的两个任意“输入变量”m和n。 但是，不同作者对这个概念的定义表明，这个词暗示的不仅仅是这个，而是（对于另外一个例子）的顺序：

精确的指令（以“计算机”理解的语言）提供快速，高效，“好”的过程，指定“计算机”（机器或人员，配备必要的内部信息和功能）的“移动” ，解码，然后处理任意输入整数/符号m和n，符号+和= ……以及“有效地”在一个“合理”时间内在指定位置和指定格式中输出整数y。
算法的概念也被用来定义可判定性的概念。 这个概念对解释正式系统是如何从一小套公理和规则开始出现的核心是很重要的。 在逻辑上，算法需要完成的时间不能被测量，因为它与我们惯常的物理尺寸没有明显的关系。 由于这种不确定性，这是描述正在进行的工作的特征，因此无法提供适合具体（某种意义上）和抽象用法的算法定义。

形式化
算法对计算机处理数据的方式至关重要。 许多计算机程序都包含一些算法，这些算法详细说明了计算机应该执行的特定指令（按特定的顺序）执行指定的任务，例如计算员工的工资支票或打印学生的报告卡。 因此，算法可以被认为是可以通过图灵完备系统模拟的任何操作序列。 主张这篇论文的作者包括Minsky（1967），Savage（1987）和Gurevich（2000）：

明斯基说：“但是，我们也会用图灵……来维持任何”自然“被称为有效的程序，事实上可以通过一个（简单的）机器来实现。尽管这看起来很极端，但是参数……其青睐很难驳斥“。

Gurevich：“…… Turing支持他的论文的非正式论证证明了一个更强的论题：每一种算法都可以用图灵机模拟…根据Savage [1987]，算法是由图灵机定义的计算过程” 。

通常，当算法与处理信息相关联时，可以从输入源读取数据，将数据写入输出设备并存储用于进一步处理。 存储的数据被视为执行该算法的实体的内部状态的一部分。 实际上，状态存储在一个或多个数据结构中。

对于某些这样的计算过程，该算法必须严格定义：以适用于可能出现的所有可能情况的方式进行规定。 也就是说，任何有条件的步骤都必须系统地处理，逐案处理; 每个案件的标准必须清晰（并可计算）。

由于算法是精确步骤的精确列表，因此计算顺序始终对算法的功能至关重要。 说明通常被认为是明确列出的，并且被描述为从“从顶部开始”并且“从底部开始”，这是一种更加正式地由控制流程描述的想法。

到目前为止，关于算法形式化的这种讨论假设了命令式编程的前提。 这是最常见的概念，它试图用离散的“机械”手段来描述任务。 这种形式化算法概念的独特之处在于赋值操作，即设置变量的值。 它来源于作为暂存器的“记忆”的直觉。 下面有一个例子。

有关构成算法的一些替代概念，请参阅函数式编程和逻辑编程。

表达算法
算法可以用多种表示法表示，包括自然语言，伪代码，流程图，drakon图表，编程语言或控制表（由解释器处理）。 算法的自然语言表达式往往是冗长而模糊的，而且很少用于复杂或技术性的算法。 伪代码，流程图，drakon图表和控制表格是结构化的表达算法，避免了自然语言陈述中常见的许多含糊之处。 编程语言主要用于以可由计算机执行的形式表达算法，但通常用作定义或记录算法的方式。

可以有各种各样的表示形式，可以将一个给定的图灵机程序表示为一系列机床表（更多地参见有限状态机，状态转换表和控制表），如流程图和drakon-charts（更多信息请参见状态图），或者作为一种称为“四极组”的基本机器代码或汇编代码的形式（更多地参见图灵机）。

算法的表示可以分为三种可接受的图灵机描述的级别：

1高​​级描述
“…散文描述算法，忽略实现细节。在这个层面上，我们不需要提及机器如何管理它的磁带或磁头。”
2实现描述
“…散文用于定义图灵机使用它的头部的方式以及它将数据存储在磁带上的方式，在这个级别上我们不提供状态或转换函数的细节。”
3形式描述
最详细的“最低级别”给出了图灵机的“状态表”。
有关在所有三个级别中描述的简单算法“添加m + n”的示例，请参阅算法＃示例。

履行
大多数算法都是用计算机程序来实现的。 然而，算法也可以通过其他手段来实现，例如在生物神经网络（例如，执行算术的人脑或寻找食物的昆虫）中，在电路中或在机械装置中。

计算机算法
在计算机系统中，算法基本上是由软件开发人员用软件编写的一个逻辑实例，以便对于预期的“目标”计算机产生来自给定（可能为空）输入的输出。 即使运行在旧硬件中的最佳算法也会产生比用于相同目的的非最佳（更高时间复杂度）算法更快的结果，运行在更高效的硬件中; 这就是计算机硬件等算法被视为技术的原因。

“优雅”（紧凑）节目，“好”（快速）节目：“简单和优雅”的概念非正式地出现在Knuth和Chaitin中：

Knuth：“……我们需要一些定义较为宽松的美学算法，其中一个标准是执行该算法所需的时间长度……其他标准是该算法对计算机的适应性，其简单性和优雅性等“
Chaitin：“……一个程序是”优雅的“，我的意思是说，它是产生输出的最小可能程序，它”
Chaitin在他的定义中写道：“我会证明你不能证明一个程序是’优雅的’” – 这样的证明可以解决Halting问题（同上）。

可通过算法计算的算法与函数：对于给定的函数，可能存在多个算法。 这是事实，即使没有扩展程序员可用的指令集。 罗杰斯指出：“它很重要的是要区分算法的概念，即过程和算法可计算的函数概念，即通过过程产生的映射，同一个函数可能有几种不同的算法。

不幸的是，善良（速度）和优雅（紧凑）之间可能存在权衡 – 一个优雅的程序可能需要更多的步骤才能完成计算，而不是一个优雅的程序。 下面是一个使用Euclid算法的例子。

计算机（和计算机），计算模型：计算机（或人称“计算机”）是一种受限制类型的机器，它是盲目遵循其指令的“离散确定性机械设备”。 Melzak和Lambek的原始模型将这个概念简化为四个要素：（i）离散的，可区分的位置，（ii）离散的，不可区分的计数器（iii）代理，以及（iv）相对于剂。

算法模拟：计算机（计算机）语言：Knuth建议读者“学习算法的最好方法就是尝试它……立即拿起笔和纸，并通过一个例子”。 但是模拟或执行真实事物呢？ 程序员必须将算法转换成模拟器/计算机/计算机可以有效执行的语言。 Stone给出了一个例子：计算二次方程的根时，计算机必须知道如何取平方根。 如果他们不这样做，那么算法要有效，必须提供一组提取平方根的规则。

这意味着程序员必须知道相对于目标计算代理（计算机/计算机）有效的“语言”。

算法分析
知道给定算法在理论上需要多少特定资源（如时间或存储）通常很重要。 已经开发了用于分析算法以获得这样的定量答案（估计）的方法; 例如，上面的排序算法具有O（n）的时间要求，使用具有n的大O标记作为列表的长度。 在任何时候，算法只需要记住两个值：迄今为止发现的最大数字，以及它在输入列表中的当前位置。 因此，如果存储输入数字所需的空间不被计算，则据说具有O（1）的空间要求，或者如果被计数则被认为是O（n）。

正式与经验
算法的分析和研究是计算机科学的一门学科，通常在不使用特定编程语言或实现的情况下抽象地实施。 从这个意义上讲，算法分析类似于其他数学学科，因为它专注于算法的基础属性，而不是任何特定实现的细节。 通常伪码被用于分析，因为它是最简单和最一般的表示法。 然而，最终，大多数算法通常是在特定的硬件/软件平台上实现的，并且他们的算法效率最终将通过真实代码进行测试。 对于“一次性”问题的解决方案，特定算法的效率可能不会产生重大后果（除非n非常大），但对于设计用于快速交互式，商业或长期科学用途的算法，这可能是至关重要的。 从小n扩展到大n常常暴露低效率的算法，否则它们是良性的。

执行效率
为了说明即使在完善的算法中可能实现的潜在改进，最近与FFT算法（在图像处理领域大量使用）有关的重大创新，可以将处理时间减少1,000倍，适用于医疗成像等应用。 一般来说，速度的提高取决于问题的特殊性质，这在实际应用中非常普遍。 这种幅度的加速使得广泛使用图像处理的计算设备（如数码相机和医疗设备）能够消耗更少的能量。

分类
有多种方法可以对算法进行分类，每种方法都有其优点。

通过实施
一种分类算法的方法是通过实施手段。

递归
递归算法是一种重复调用（引用）自身直到某个条件（也称为终止条件）匹配的算法，这是函数式编程的一种常用方法。 迭代算法使用循环等重复结构，有时候还会使用像堆栈这样的附加数据结构来解决给定的问题。 一些问题自然适合于一种实现或另一种实现。 例如，河内的塔楼很好理解使用递归实现。 每个递归版本都有一个等价的（但可能更多或更不复杂）迭代版本，反之亦然。

合乎逻辑
算法可以被看作受控逻辑推理。 这个概念可以表示为：算法=逻辑+控制。 逻辑组件表达可以在计算中使用的公理，并且控制组件确定对公理应用推演的方式。 这是逻辑编程范例的基础。 在纯粹的逻辑编程语言中，控制组件是固定的，算法是通过仅提供逻辑组件来指定的。 这种方法的吸引力是优雅的语义：公理的变化在算法中有明确的变化。

串行，并行或分布式
算法通常是在假设计算机一次执行一条算法指令的情况下进行讨论的。 这些计算机有时被称为串行计算机。 针对这种环境设计的算法被称为串行算法，而不是并行算法或分布式算法。 并行算法利用计算机体系结构，其中几个处理器可以同时处理一个问题，而分布式算法则利用与计算机网络连接的多台机器。 并行或分布式算法将问题分为更多对称或不对称的子问题，并将结果收集在一起。 这种算法中的资源消耗不仅是每个处理器上的处理器周期，还包括处理器之间的通信开销。 一些排序算法可以高效地并行化，但是它们的通信开销是昂贵的。 迭代算法通常是可并行的。 有些问题没有并行算法，被称为固有序列问题。

确定性或非确定性
确定性算法通过在算法的每一步精确决定来解决问题，而非确定性算法通过猜测来解决问题，尽管通过使用启发式技术可以使典型猜测更加准确。

准确或近似
尽管许多算法都达到了精确的解决方案，但近似算法会寻求更接近真实解决方案的近似算法。 逼近可以通过使用确定性或随机策略来实现。 这样的算法对于许多难题具有实际价值。 近似算法的一个例子是背包问题。 在有一组给定项目的情况下，背包问题是一个问题。 问题的目标是打包背包以获得最大总价值。 每件产品都有一定的重量和一些价值。 我们可以承载的总重量不超过某个固定数量X.因此，我们必须考虑物品的重量以及它们的价值。

量子算法
他们运行在一个现实的量子计算模型上。 该术语通常用于那些看起来固有量子化的算法，或者使用量子计算的一些基本特征，如量子叠加或量子纠缠。

按设计范例
分类算法的另一种方式是通过其设计方法或范例。 有一定范例，各有不同。 此外，这些类别中的每一类都包含许多不同类型的算法。 一些常见的范例是：

蛮力或穷举搜索
这是尝试每种可能的解决方案来看哪个最好的天真方法。

分而治之
一个分而治之的算法不断地将一个问题的实例减少到同一个问题的一个或多个较小的实例（通常是递归的），直到实例足够小以容易解决。 分而治之的一个例子就是合并排序。 在将数据划分成片段之后，可以对每个数据片段进行排序，并且通过合并片段可以在征服阶段获得整个数据的排序。 分而治之的简单变体称为减少和征服算法，它解决了一个相同的子问题，并使用这个子问题的解决方案来解决更大的问题。 分而治之将问题分解为多个子问题，因此征服阶段比减少和征服算法更为复杂。 减法和征服算法的一个例子是二进制搜索算法。

搜索和枚举
许多问题（如下棋）可以模拟为图形上的问题。 图探索算法规定了围绕图移动的规则，对于这些问题很有用。 该类别还包括搜索算法，分支和界限枚举和回溯。
随机算法

降低复杂性
这种技术涉及通过将其转化为一个更好的已知问题来解决一个难题，我们有（希望）渐近最优算法。 目标是找到一个减少算法，其复杂性不会由最终的简化算法所支配。 例如，用于在未排序列表中查找中位数的一种选择算法涉及首先对列表（昂贵部分）进行排序，然后拉出排序列表（廉价部分）中的中间元素。 这种技术也被称为变形和征服。

优化问题
对于优化问题，有一个更具体的算法分类; 针对这些问题的算法可能落入上面描述的一个或多个一般类别以及以下之一：

线性规划
当搜索线性等式和不等式约束的线性函数的最优解时，问题的约束可以直接用于产生最优解。 有一些算法可以解决此类别中的任何问题，例如流行的单纯形算法。 线性规划可以解决的问题包括有向图的最大流问题。 如果问题还需要一个或多个未知数必须是整数，那么它将被分类为整型编程。 线性规划算法可以解决这样的问题，如果可以证明所有对整数值的限制都是肤浅的，即解决方案无论如何满足这些限制。 在一般情况下，根据问题的难度，使用专门的算法或找到近似解的算法。
动态编程

当一个问题表现出最佳的子结构时 – 意味着问题的最优解可以从最优解到子问题 – 以及重叠的子问题构成，这意味着相同的子问题用于解决许多不同的问题实例，一种称为动态编程的更快速方法避免了重新计算解决方案已经被计算出来了。 例如，Floyd-Warshall算法是通过使用从所有相邻顶点到目标的最短路径来找到加权图中从顶点到目标的最短路径。 动态编程和记忆汇集在一起​​。 动态规划和分而治之的主要区别在于，子问题在分而治之中或多或少是独立的，而子问题在动态规划中是重叠的。 动态编程和直接递归之间的区别在于递归调用的缓存或记忆。 当子问题是独立的并且没有重复时，记忆并没有帮助; 因此动态编程不是解决所有复杂问题的方法。 通过使用记忆或维护已经解决的子问题表，动态规划将许多问题的指数性质降低至多项式复杂度。

贪婪的方法
贪婪算法与动态规划算法类似，它通过检查子结构来工作，在这种情况下不是问题，而是给定解决方案。 这些算法从一些解决方案开始，这些解决方案可以以某种方式给出或构建，并通过进行小的修改来改进它。 对于某些问题，他们可以找到最佳解决方案，而对于其他问题，他们可以停止在局部最优解，即解决方案无法通过算法改进，但不是最佳解决方案。 贪婪算法最普遍的用途是寻找最小生成树，在这种方法中可以找到最优解。 Huffman树，Kruskal，Prim，Sollin是可以解决这个优化问题的贪婪算法。

启发式方法
在优化问题中，在寻找最佳解决方案不切实际的情况下，启发式算法可用于找到接近最优解的解。 这些算法在进展中越来越接近最佳解决方案。 原则上，如果运行了无限的时间，他们会找到最佳解决方案。 他们的优点是他们可以在相对较短的时间内找到非常接近最佳解决方案的解决方案。 这些算法包括局部搜索，禁忌搜索，模拟退火和遗传算法。 其中一些，如模拟退火，是非确定性算法，而其他的，如禁忌搜索，是确定性的。 当非最优解的误差的界限已知时，该算法被进一步分类为近似算法。

按研究领域
科学的每个领域都有自己的问题，需要高效的算法。 一个领域的相关问题经常一起研究。 一些示例类是搜索算法，排序算法，合并算法，数值算法，图算法，字符串算法，计算几何算法，组合算法，医学算法，机器学习，密码学，数据压缩算法和解析技术。

字段倾向于彼此重叠，并且算法在一个字段中的进步可以改善其他字段（有时完全不相关的字段）的字段。 例如，动态编程是为了优化工业资源消耗而发明的，但现在用于解决许多领域的广泛问题。

由复杂性
算法可以根据他们需要完成的时间量与其输入大小进行比较：

常量时间：如果算法所需的时间相同，则无论输入大小如何。 例如对数组元素的访问。
线性时间：如果时间与输入大小成比例。 例如列表的遍历。
对数时间：如果时间是输入大小的对数函数。 例如二进制搜索算法。
多项式时间：如果时间是输入大小的功率。 例如，气泡排序算法具有二次时间复杂度。
指数时间：如果时间是输入大小的指数函数。 例如蛮力搜索。
一些问题可能具有不同复杂度的多种算法，而其他问题可能没有算法或者没有已知的有效算法。 还有一些问题到其他问题的映射。 由于这个原因，人们发现它更适合将问题本身分类，而不是根据最佳算法的复杂性将算法分类为等价类。

连续算法
应用于“算法”一词时，形容词“连续”可以表示：

即使这些数据是用离散近似表示的，这些算法在数值分析中被研究， 要么
一种运算在模拟计算机上以微分方程形式运行的算法，该算法可以连续运行数据。