在数学和计算机科学中，算法是解决一类问题的明确说明。算法可以执行计算、数据处理、自动推理和其他任务。
作为一种有效的方法，一种算法可以在有限的空间和时间内，用一种定义良好的形式语言表示，用于计算一个函数从初始状态和初始输入（可能为空）开始，指令描述了一种计算，当执行时，通过有限个定义进行计算，最终产生“输出”，并最终在结束状态终止。从一个状态到下一个状态的转换不一定是确定性的；一些被称为随机化算法的算法结合了随机输入。
算法的概念已经存在了几个世纪。希腊数学家使用埃拉托斯滕斯筛中的算法来寻找素数，使用欧几里得算法来寻找两个数的最大公约数。
单词algorithm本身源自9世纪的数学家。部分形式化成为现代算法的概念始于试图解决由大卫希尔伯特在年提出的Entscheidungsproblem（决策问题）。后来的形式化是试图定义“有效的可计算性”或“有效的方法”。这些形式化包括、和年的G_del–Herbrand–Kleene递归函数、年的AlonzoChurch的lambda微积分、年的EmilPost公式1以及-37和年的AlanTuring机器。
缘起
“算法”一词的词源于将穆罕默德伊本穆萨的名字拉丁化，这是到Algorismus的第一步，他是波斯数学家、天文学家、地理学家和学者。
大约年，al-khwarizmi写了一篇关于印度教-阿拉伯数字系统的阿拉伯语论文，在12世纪被翻译成拉丁语，标题为algoritmidenumeroindorum。这个标题的意思是“印地安人的数字上的算法”，其中“算法”是翻译al-khwarizmi名字的拉丁化。选择他的名字，简单的意思是“十进制数字系统”。15世纪，在希腊语单词“算术”的影响下，拉丁语单词改为algorithmus，相应的英语术语“算法”在17世纪首次得到证实；19世纪引入了现代意义。
在英语中，它最初在年被使用，然后在年被使用。英语采用了法语术语，但直到19世纪末，“算法”才有了现代英语的含义。
这个词的另一个早期用法是年，在亚历山大德维尔迪欧撰写的名为《卡门·德阿尔戈里斯莫》的手册中。由此开始：
算法主义是目前我们使用印度数字2乘以5的艺术。
这首诗有几百行长，总结了印度骰子，塔利布斯印度语，或印度数字的新风格计算的艺术。
非正式定义
非正式的定义可以是“一组精确定义操作序列的规则”。包括所有计算机程序，包括不执行数值计算的程序。通常，程序只有在最终停止时才是一种算法。
一个典型的算法例子是欧几里得算法，用于确定两个整数的最大公因数；后面的章节例子描述了这个算法（还有其他的例子）。
Boolos，Jeffrey，在以下引文中提供了该词的非正式含义：
没有人能写得足够快、足够长或足够小（“越来越小，没有限制……你应该试着写在分子、原子、电子上”），列出一个可枚举的无限集合的所有成员，用一些符号一个接一个地写下他们的名字。但是人类可以做同样有用的事情，在某些可枚举的无限集合的情况下：他们可以给出明确的指令来确定集合的第n个成员，对于任意有限的n。这些指令要非常明确地给出，在某种形式下，它们可以被一台计算机跟随，或者由一个能够驾驶汽车的人跟随。只对符号进行非常基本的运算。
“可枚举无限集”是其元素可以与整数一一对应的集合。因此，Boolos和Jeffrey说，一个算法暗示了一个过程的指令，该过程从一个或多个任意的“输入”整数“创建”输出整数，理论上，这些整数可以任意大。因此，一个算法可以是一个代数方程，例如y=m+n——两个任意的“输入变量”m和n，它们产生一个输出y。但是，不同作者试图定义这个概念，表明这个词的含义远不止这个，它的顺序是（例如加法）：
精确的指令（用“计算机”所理解的语言表示）。对于一个快速、高效、良好的过程，该过程规定了“计算机”的“移动”（机器或人，具有必要的内部信息和能力）。查找、解码，然后处理任意输入整数/符号m和n、符号+和=…以及“有效地”在“合理的”时间内，在指定的地点，以指定的格式，产生个整数y。
算法的概念也被用来定义可判定性的概念。这个概念对于解释正式系统是如何从一组小的公理和规则开始形成的至关重要。在逻辑上，一个算法需要完成的时间是无法测量的，因为它显然与我们习惯的物理维度无关。由于这些不确定性，即正在进行的工作的特征，导致算法定义不可用，既适合具体（在某种意义上）又适合术语的抽象用法。
形式化
算法对于计算机处理数据的方式至关重要。许多计算机程序都包含详细说明计算机执行特定任务（按特定顺序）应执行的特定指令的算法，例如计算员工工资或打印学生报告卡。因此，一个算法可以被认为是任何可以被图灵完整系统模拟的操作序列。主张这篇论文的作者包括明斯基（年）、萨维奇（年）和古列维奇（年）：
明斯基：“但我们也会保持，图灵……任何可以“自然”被称为有效的过程，实际上都可以通过（简单的）机器来实现。虽然这看起来很极端，但争论…对它有利是很难反驳的。
古列维奇：“…图灵支持他的论文的非正式论点证明了一个更强有力的论点：每种算法都可以被图灵机器模拟……根据Savage，算法是由图灵机定义的计算过程。
通常，当算法与处理信息相关联时，可以从输入源读取数据，写入输出设备，并存储数据以进行进一步处理。存储的数据被视为执行算法的实体的内部状态的一部分。实际上，状态存储在一个或多个数据结构中。
对于某些这样的计算过程，必须严格定义算法：以它在所有可能出现的情况下应用的方式指定。也就是说，任何有条件的步骤都必须系统地逐个处理；每种情况的标准必须是明确的（并且是可计算的）。
由于算法是精确步骤的精确列表，因此计算顺序对算法的运行始终至关重要。通常假定指令被明确地列出，并且被描述为“从上到下”的开始，这是一种更正式地由控制流描述的思想。
到目前为止，对算法形式化的讨论假定了命令式编程的前提。这是最常见的概念，它试图用离散的“机械”的方式来描述一个任务。对于这种形式化算法的概念来说，唯一的一点就是赋值操作，即设置变量的值。它源于“记忆”作为草稿的直觉。下面有这样一个例子。
有关构成算法的其他概念，请参阅函数编程和逻辑编程。
表示算法
算法可以用多种符号表示，包括自然语言、伪代码、流程图、Drakon图、编程语言或控制表（由译员处理）。算法的自然语言表达往往是冗长和模棱两可的，很少用于复杂或技术算法。伪代码、流程图、drakon图和控制表是表示算法的结构化方法，避免了自然语言语句中常见的许多不明确之处。编程语言主要用于以计算机可以执行的形式表示算法，但通常用作定义或记录算法的方法。
有各种各样的表示可能，人们可以将给定的图灵机程序表示为一系列机器表（更多见有限状态机、状态转换表和控制表）、流程图和drakon图（更多见状态图）或称为“q集”的基本机器代码或汇编代码的形式。
算法的表示可分为图灵机器描述的三个可接受级别：
高级描述
“忽略实现细节。在这个层次上，我们不需要提及机器如何管理其磁带或磁头。”
实现描述
“用于定义图灵机使用其头部的方式以及在磁带上存储数据的方式。在这个层次上，我们不提供状态或过渡函数的细节。”
正式描述
最详细的“最低级别”给出了图灵机的“状态表”。
有关所有三个级别中描述的简单算法“添加m+n”的示例，请参见算法示例。
设计
算法设计是指求解问题的一种方法或数学过程以及工程算法。算法的设计是运筹学许多解理论的一部分，如动态规划、分治等。设计和实现算法设计的技术也称为算法设计模式，例如模板方法模式和装饰器模式。
算法设计的一个最重要的方面是创建一个具有高效运行时的算法，也称为大O。
算法开发的典型步骤：
问题定义模型的开发算法说明设计算法检查算法的正确性算法分析算法的实现程序测试文件准备实现
大多数算法都是作为计算机程序来实现的。然而，算法也可以通过其他方式实现，例如在生物神经网络（例如，人脑实现算法或昆虫寻找食物）、电路或机械装置中。
计算机算法
在计算机系统中，算法基本上是软件开发人员在软件中编写的逻辑实例，对于预期的“目标”计算机从给定的（可能为空）输入产生输出是有效的。即使是在旧硬件中运行的优化算法，也会比在更高效的硬件中运行的非最优（时间复杂度更高）算法产生更快的结果；这就是为什么算法（如计算机硬件）被视为技术的原因。
“优雅”（紧凑）程序，“良好”（快速）程序：在克努斯非正式地出现“简单和优雅”的概念，如此：
Knuth：“……我们需要一些定义松散的美学意义上的好算法。一个标准…是执行算法所用的时间长度…其他标准包括算法对计算机的适应性、简单性和优雅性等。
Chaitin：“……一个程序是“优雅的”，我的意思是它是产生输出的最小可能的程序。
在他的定义前加了一句话：“我将向你展示，你无法证明一个程序是‘优雅的’”——这样的证明可以解决停顿问题（同上）。
算法与可由算法计算的函数：对于给定的函数，可能存在多个算法。这是真的，即使没有扩展可供程序员使用的指令集。罗杰斯观察到“这是…重要的是要区分算法的概念，即过程和可由算法计算的函数的概念，即由过程生成的映射。同一个函数可能有几个不同的算法。
不幸的是，在好（速度）和优雅（紧凑）之间可能存在一种权衡——一个优雅的程序可能需要更多的步骤来完成计算，而不是一个不那么优雅的程序。下面是一个使用欧几里得算法的例子。
计算模型：计算机是一种受限制的机器，是一种盲目遵循其指令的“离散确定性机械装置”。不可区分的计数器代理和相对于代理的能力有效的指令列表。
明斯基在他的“非常简单的可计算性基础”中描述了兰贝克的“算盘”模型的一个更为契合的变体。除了停止之外，明斯基的机器还包括三种分配操作：零（例如，被0:L←0替换的位置的内容）、继承者（例如，L←L+1）和减量（例如，L←L1）。程序员很少需要用如此有限的指令集编写“代码”。但明斯基（和梅尔扎克和兰贝克一样）表明，他的机器只有四种基本类型的指令：条件goto、无条件goto、分配/替换/替换和停止。
模拟算法：计算机（Computor）语言：Knuth建议读者“学习算法的最佳方法是尝试它”。…立即拿笔和纸做一个例子，但模拟或执行真实的东西呢？程序员必须将算法翻译成模拟器/计算机/计算机可以有效执行的语言。斯通举了一个例子：当计算二次方程的根时，计算机必须知道如何取平方根。如果不这样做，那么算法必须提供一组规则来提取平方根，才能有效地发挥作用。
这意味着程序员必须知道相对于目标计算代理（计算机/计算机）有效的“语言”。
但是模拟应该使用什么模型呢？vanEmdeBoas观察到，“即使我们把复杂性理论建立在抽象的基础上而不是具体的机器上，模型选择的任意性仍然存在。此时，模拟的概念进入了，当测量速度时，指令集很重要。例如，欧几里得算法中计算余数的子程序执行速度要快得多，如果程序员有一个“模”指令，而不仅仅是减法（或者更糟的是：只有明斯基的“减法”）。
结构化编程、规范结构：根据丘奇-图灵理论，任何算法都可以通过已知图灵完备的模型来计算，并且根据明斯基的演示，图灵完备只需要四种指令类型：条件goto、无条件goto、赋值、停止。Kemeny和Kurtz观察到，虽然无条件goto和有条件if-thengoto的“无纪律”使用会导致“意大利面条代码”，但是程序员可以只使用这些指令编写结构化程序；另一方面，“用结构化语言编写结构化差的程序也可能，而且不太难。”Tausworthe增加了三个规范结构：序列、if-then-else和while-do，还有两个：do-while和case。结构化程序的另一个好处是，它使用数学归纳法来证明正确性。
标准流程图符号：图形辅助工具称为流程图，提供了描述和记录算法（以及一个计算机程序）的方法。就像minsky机器的程序流程一样，流程图总是从页面的顶部开始向下。它的主要符号只有四个：显示程序流的定向箭头、矩形（序列、GoTo）、菱形（if-then-else）和点（或tie）。标准结构由这些原始形状构成。子结构可以“嵌套”成矩形，但前提是上部结构只有一个出口。符号及其用于构建规范结构的用途如图所示。
例子
算法示例
最简单的算法之一是在随机顺序的数字列表中找到最大的数字。找到解决方案需要查看列表中的每个数字。由此得出一个简单的算法，可以用英语散文的高级描述来说明，如下所示：
高层次的描述：
如果集合中没有数字，则没有最高数字。假设集合中的第一个数字是集合中最大的数字。对于集合中的每个剩余数字：如果此数字大于当前最大数字，则将此数字视为集合中的最大数字。当集合中没有要迭代的数字时，请将当前最大的数字视为集合中最大的数字。（准）形式描述：用散文写，但更接近于计算机程序的高级语言，以下是用伪代码或pidgin代码对算法进行更正式的编码：
“←”表示分配。例如，“最大←项”是指最大值的值变化到项的值。“返回”终止算法并输出以下值。
欧几里得算法
欧几里得计算两个数的最大公约数（gcd）的算法在其元素的第七卷（“初等数理论”）中出现。欧几里得提出了这样一个问题：“给定两个数互不相乘，以找到它们的最大公约数。”他定义“一个由单位组成的多个数”：一个计数数，一个不包括零的正整数。“测量”是将较短的测量长度s沿较长的长度l连续放置（q次），直到剩余部分r小于较短的长度。在现代词汇中，余数r=lq×s，q是商，或余数r是“模”，即除法后剩余的整数分数部分。
为了使欧几里得方法成功，起始长度必须满足两个要求：长度不能为零，并且减法必须是“适当的”；即，测试必须保证两个数字中较小的数字从较大的数字中减去（或者，两个数字可以相等，以便减法得出零）。
欧几里得的原始证明又增加了第三个要求：两个长度不能是素数。欧几里得规定了这一点，这样他就可以建立一个约简和荒谬的证据，证明两个数字的共同度量实际上是最大的。虽然尼科马丘斯的算法与欧几里得的算法相同，但当这些数字互为素数时，就产生了它们共同度量的数字“1”。所以，准确地说，下面的算法确实是尼科马丘斯的算法。
欧几里得算法的计算机语言
执行欧几里得算法只需要几个指令类型：一些逻辑测试（条件goto）、无条件goto、赋值（替换）和减法。
位置用大写字母表示，例如S、A等。
一个地点的不同数量（数字）用小写字母书写，并且（通常）与该地点的名称相关。例如，起始位置L可能包含数字L=。
欧几里得算法的一个差程序
以下算法的框架是Knuth的Euclid’s和Ni