算法
算法（英语：algorithm），在数学（算学）和计算机科学之中，指一个被定义好的、计算机可施行其指示的有限步骤或次序[1]，常用于计算、数据处理和自动推理。算法可以使用条件语句通过各种途径转移代码执行（称为自动决策），并推导出有效的推论（称为自动推理），最终实现自动化。
相反，启发式是一种解决问题的方法，可能没有完全指定，也可能不能保证正确或最优的结果，尤其是在没有明确定义的正确或最优结果的问题领域。[2]例如，社交媒体推荐系统依赖于启发式，尽管在21世纪的流行媒体中被广泛称为算法，但由于问题的性质，它无法提供正确的结果。
早在尝试解决希尔伯特提出的判定问题时，算法的不完整概念已经初步定型；在其后的正式化阶段中人们尝试去定义“有效可计算性[3]”或者“有效方法[4]”。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数，阿隆佐·邱奇于1936年提出的λ演算，1936年埃米尔·莱昂·珀斯特的波斯特-图灵机和艾伦·图灵1937年提出的图灵机。即使在当下，依然常有符合直觉的想法难以定义为形式化算法的情况。[5]
算法是有效方法，包含一系列定义清晰的指令[6]，并可于有限的时间及空间内清楚的表述出来[7]。算法中的指令描述的是一个计算，它执行时从一个初始状态和初始输入（可能为空）开始，[8]经过一系列有限[9]而清晰定义的状态最终产生输出[10]并停止于一个终态。 一个状态到另一个状态的转移不一定是确定的。 包括随机化算法在内的一些算法，都包含了一些随机输入。[11][12]
历史
编辑算法在中国古代文献中称为“术”，最早出现在《周髀算经》、《九章算术》。特别是《九章算术》，给出四则运算、最大公约数、最小公倍数、开平方根、开立方根、求素数的埃氏筛，线性方程组求解的高斯消元法。三国时代的刘徽给出求圆周率的算法：刘徽割圆术。
自唐代以来，历代更有许多专门论述“算法”的专著：
- 唐代：《一位算法》 一卷，《算法》 一卷；
- 宋代：《算法绪论》 一卷、《算法秘诀》 一卷；最著名的是杨辉的《杨辉算法》；
- 元代：《丁巨算法》；
- 明代：程大位 《算法统宗》
- 清代：《开平算法》、《算法一得》、《算法全书》。
而英文名称“algorithm”来自于9世纪波斯数学家花拉子米（比阿勒·霍瓦里松，波斯语：خوارزمی ，拉丁转写：al-Khwarizmi），因为比阿勒·霍瓦里松在数学上提出了算法这个概念。“算法”原为“algorism”，即“al-Khwarizmi”的音转，意思是“花剌子模的”运算法则，在18世纪演变为“algorithm”。
欧几里得算法被人们认为是史上第一个算法。
第一次编写程序是爱达·勒芙蕾丝（Ada Byron）于1842年为巴贝奇分析机编写求解解伯努利微分方程的程序，因此爱达·勒芙蕾丝被大多数人认为是世界上第一位程序员[13]。因为查尔斯·巴贝奇（Charles Babbage）未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。 因为“well-defined procedure”缺少数学上精确的定义，19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题，并提出一种假想的电脑的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要的作用。
特征
编辑以下是高德纳在他的著作《计算机程序设计艺术》里对演算法的特征归纳：
基本要素
编辑算法的核心是建立问题抽象的模型和明确求解目标，之后可以根据具体的问题选择不同的模式和方法完成算法的设计。
常用设计模式
编辑完全遍历法和不完全遍历法：在问题的解是有限离散解空间，且可以验证正确性和最优性时，最简单的算法就是把解空间的所有元素完全遍历一遍，逐个检测元素是否是我们要的解。这是最直接的算法，实现往往最简单。但是当解空间特别庞大时，这种算法很可能导致工程上无法承受的计算量。这时候可以利用不完全遍历方法——例如各种搜索法和规划法——来减少计算量。 分治法：把一个问题分割成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。 动态规划法：当问题的整体最优解就是由局部最优解组成的时候，经常采用的一种方法。贪婪算法：常见的近似求解思路。当问题的整体最优解不是（或无法证明是）由局部最优解组成，且对解的最优性没有要求的时候，可以采用的一种方法。 线性规划法：见条目。 简并法：把一个问题通过逻辑或数学推理，简化成与之等价或者近似的、相对简单的模型，进而求解的方法。
常用实现方法
编辑递归方法与迭代方法 顺序计算、并行计算和分布式运算：顺序计算就是把形式化算法用程序设计语言进行单线程序列化后执行。 确定性算法和非确定性算法 精确求解和近似求解
形式化算法
编辑算法是电脑处理信息的本质，因为计算机程序本质上是一个算法来告诉电脑确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。一般地，当算法在处理信息时，会从输入装置或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。
复杂度
编辑时间复杂度
编辑算法的时间复杂度是指算法需要消耗的时间资源。一般来说，电脑算法是问题规模 的函数 ，算法的时间复杂度也因此记做 ： 算法执行时间的增长率与 的增长率正相关，称作渐近时间复杂度，简称时间复杂度。 常见的时间复杂度有：常数阶 ，对数阶 ，线性阶 ，线性对数阶 ，平方阶 ，立方阶 ，…， 次方阶 ，指数阶 。随着问题规模 的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
空间复杂度
编辑算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。
实现
编辑示例
编辑求最大值演算法
编辑这是算法的一个简单的例子。 我们有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数位看成是一颗豆子的大小，可以将下面的算法形象地称为“捡豆子”：
- 首先将第一颗豆子放入口袋中。
- 从第二颗豆子开始检查，如果正在检查的豆子比口袋中的还大，则将它捡起放入口袋中，同时丢掉原先口袋中的豆子。反之则继续下一颗豆子。直到最后一颗豆子。
- 最后口袋中的豆子就是所有的豆子中最大的一颗。以上算法在中国大陆的教科书中通常被叫做“打擂法”或者“循环打擂”[14][15][16]：在一个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;
}
求最大公约数演算法
编辑求两个自然数的最大公约数 设两个变量 和
- 如果 ，则交换 和
- 除以 ，得到余数
- 判断 ，正确则 即为“最大公约数”，否则下一步
- 将 赋值给 ，将 赋值给 ，重做第一步。
用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;
}
分类
编辑分类算法有多种方法，每种方法都有自己的优点。
通过实施
编辑分类算法的一种方法是通过实现手段。
int gcd（int A, int B） {
if （B == 0）
return A;
else if （A > B）
return gcd（A-B,B）;
else
return gcd（A,B-A）;
}
|
| 从上面的流程图递归 C 实现欧几里得算法 |
- 递归
- 递归算法是一种重复调用（引用）自身的算法，直到某个条件（也称为终止条件）匹配，这是函数式编程常用的方法。迭代算法使用循环之类的重复构造，有时使用堆栈之类的附加数据结构来解决给定的问题。有些问题自然适合于这种或那种实现。例如，使用递归实现可以很好地理解河内的塔。每个递归版本都有一个等价的（但可能或多或少复杂）迭代版本，反之亦然。
- 串联的、平行的或分布的
- 算法通常是在假设计算机一次执行一条算法指令的情况下讨论的。那些计算机有时被称为串行计算机。针对这种环境设计的算法称为串行算法，而不是并行算法或分布式算法。并行算法是利用计算机体系结构的算法，其中多个处理器可以同时处理一个问题。分布式算法是使用与计算机网络连接的多台机器的算法。并行和分布式算法将问题划分为更加对称或不对称的子问题，并将结果收集在一起。例如，CPU 就是并行算法的一个例子。这种算法的资源消耗不仅是每个处理器上的处理器周期，而且是处理器之间的通信开销。有些排序算法可以有效地并行化，但是它们的通信开销很大。迭代算法通常是可并行的，但有些问题没有并行算法，称为固有的串行问题。
- 确定的或不确定的
- 确定性算法在算法的每一步都用精确的决策来解决问题，而非确定性算法通过猜测来解决问题，虽然通过启发式使典型的猜测更加精确。
- 精确的或近似的
- 虽然许多算法达到一个精确的解决方案，近似算法寻求一个近似，更接近真正的解决方案。这种近似可以通过使用确定性策略或随机策略来实现。这些算法对许多难题都有实用价值。近似算法的一个例子是背包问题，其中有一组给定的项目。它的目标是包装背包，以获得最大的总价值。每个物品都有一定的重量和价值。可携带的总重量不超过某个固定数字 X，因此，解决方案必须考虑物品的重量及其价值。[17]
- 量子算法
- 量子算法运行在一个现实的量子计算模型上。这个术语通常用于那些本质上似乎是量子的算法，或者使用量子计算的一些基本特性，如态叠加原理或量子纠缠。
通过设计范例
编辑对算法进行分类的另一种方法是通过它们的设计方法或范例。有一定数量的范例，每一个不同于其他。此外，这些类别中的每一个都包括许多不同类型的算法。一些常见的范例是:
- 暴力搜查或彻底搜查
- 蛮力是一种解决问题的方法，包括系统地尝试每一种可能的选择，直到找到最佳解决方案。这种方法可能非常耗时，因为它需要遍历所有可能的变量组合。但是，当其他方法不可用或过于复杂时，常常使用这种方法。蛮力可以用来解决各种问题，包括寻找两点之间的最短路径和破解密码。
- 各个击破
- 分而治之的算法重复地将一个问题的实例减少为同一个问题的一个或多个更小的实例（通常是递归的） ，直到这些实例足够小以便于解决。分而治之的一个例子是合并排序。在将数据分割成片段后，可以对每个片段进行排序，在征服阶段通过合并片段可以对整个数据进行排序。一种更简单的分而治之的算法称为减而治算法，它解决一个相同的子问题，并使用这个子问题的解决方案来解决更大的问题。分治算法将问题划分为多个子问题，因此分治阶段比减少分治算法复杂。递减和征服算法的一个例子是二进制搜索算法。
- 搜索和枚举
- 许多问题（比如下棋）可以建模为图形上的问题。图探索算法规定了在图中移动的规则，对于这类问题非常有用。这一类别还包括搜索算法、分支和界枚举以及回溯。
- 随机算法
- 这样的算法随机（或伪随机）做出一些选择。它们可以非常有用地找到近似解决方案的问题，找到精确的解决方案可能是不切实际的（见下面的启发式方法）。对于其中的一些问题，我们知道最快的近似必须包含一些随机性。[18] 对于某些问题，具有多项式时间复杂度的随机算法能否成为最快的算法，是一个被称为“ P/NP问题”的悬而未决的问题。这种算法有两大类:
- 蒙特卡罗算法以高概率返回正确答案。例如 RP 是这些运行在多项式时间的子类。
- 拉斯维加斯算法总是返回正确的答案，但他们的运行时间只是概率约束，例如 ZPP。
- 降低复杂性
- 这种技术涉及到通过将一个困难问题转化为一个更广为人知的问题来解决它，我们（希望）已经有了渐近最优算法。目标是找到一种复杂度不受所得到的简化算法控制的简化算法。例如，一种用于在未排序列表中查找中值的选择算法首先对列表进行排序（代价较高的部分） ，然后取出排序列表中的中间元素（代价较低的部分）。这种技术也被称为转换和征服。
- 反向追踪
- 在这种方法中，多个解决方案是逐步构建的，当确定它们不能生成有效的完整解决方案时，就会放弃这些解决方案。
优化问题
编辑对于最优化问题，有一个更具体的算法分类; 这类问题的算法可能属于上述一个或多个一般类别，也可能属于以下类别之一:
- 线性规划
- 当搜索受线性等式和不等式约束的线性函数的最优解时，该问题的约束可以直接用于产生最优解。有一些算法可以解决这类问题，比如流行的单纯形法。[19] 线性规划可以解决的问题包括有向图的最大流问题。如果一个问题额外要求一个或多个未知数必须是一个整数，那么它被分类为整数规划。一个线性规划算法可以解决这样的问题，如果它可以证明所有的限制整数值是表面的，即，解决方案满足这些限制。在一般情况下，根据问题的难度，使用专门的算法或找到近似解的算法。
- 动态编程
- 当一个问题显示出最优子结构ーー意味着一个问题的最优解可以从子问题的最优解构造出来ーー和重叠子问题，意味着同一个子问题可以用来解决许多不同的问题实例时，一种叫做动态规划的快速方法可以避免重新计算已经计算出来的解。例如，Floyd-Warshall 算法，在一个加权图中，通过使用从所有相邻顶点到达目标的最短路径，可以找到从一个顶点到达目标的最短路径。动态编程和制表一起使用。动态规划与分治的主要区别在于子问题在分治中或多或少是独立的，而子问题在动态规划中是重叠的。动态编程和简单递归的区别在于递归调用的缓存或制表。当子问题是独立的并且没有重复时，制表不起作用; 因此动态编程不是所有复杂问题的解决方案。通过使用制表法或维护已经解决的子问题表，动态规划将许多问题的指数性质降低到多项式复杂度。
- 贪婪的方法
- 贪婪算法类似于动态规划算法，它通过检查子结构来工作，在这种情况下，不是检查问题，而是检查给定的解。这种算法从某种解开始，这种解可能已经给出或已经以某种方式构造出来，然后通过小的修改对其进行改进。对于一些问题，他们可以找到最优解，而对于其他问题，他们停留在局部最优，也就是说，在解决方案，不能改进的算法，但不是最优的。贪婪算法最常用的用途是寻找最小生成树，在这种方法中可以找到最优解。霍夫曼树，克鲁斯卡尔，普里姆，Sollin 是贪婪的算法，可以解决这个最佳化问题。
- 启发式方法
- 在优化问题中，如果不能找到最优解，可以使用启发式算法来寻找接近最优解的解。这些算法的工作原理是随着它们的进展越来越接近最优解。原则上，如果运行无限长的时间，他们会找到最优解。它们的优点是能够在相对较短的时间内找到一个非常接近最优解的解。这些算法包括本地搜索、禁忌搜索、模拟退火搜索和遗传算法。其中一些算法，如模拟退火，是非确定性算法，而其他的，如禁忌搜索，是确定性的。当非最优解的误差界限已知时，该算法进一步被归类为近似演算法。
通过研究领域
编辑每个科学领域都有自己的问题，需要高效的算法。一个领域中的相关问题经常被一起研究。一些示例类是搜索算法、排序算法、合并算法、数值算法、图形算法、字符串算法、计算几何算法、组合算法、医学算法、机器学习、密码学、数据压缩算法和解析技术。
字段之间往往相互重叠，一个字段的算法进步可能会改进其他字段的算法，有时候这些字段完全不相关。例如，动态规划是为了优化工业中的资源消耗而发明的，但是现在被用于解决许多领域中的广泛问题。
通过复杂性
编辑算法可以根据它们需要完成的时间和它们的输入大小进行分类:
- 常数时间: 如果算法所需的时间相同，则不管输入大小如何。例如，对数组元素的访问。
- 对数时间: 如果时间是输入大小的对数函数。二进制搜索算法。
- 线性时间: 如果时间与输入大小成正比。列表的遍历。
- 多项式时间: 如果时间是输入大小的幂次。例如，气泡排序算法具有二次时间复杂度。
- EXPTIME: 如果时间是输入大小的指数函数。例如暴力搜索法。
一些问题可能有多个不同复杂度的算法，而另一些问题可能没有算法或者没有已知的有效算法。还有从一些问题到其他问题的映射。由于这个原因，我们发现根据问题的最佳可能算法的复杂性，将问题本身分类比将算法分为等价类更为合适。
连续算法
编辑形容词“连续”用于“算法”一词时，可以表示:
- 对表示连续数量的数据进行操作的算法，即使这些数据是由离散近似表示的ーー这种算法是在数值分析中研究的; 或
- 一种微分方程形式的算法，在模拟计算机上运行，不断地对数据进行操作。[20]
参考文献
编辑- ^ 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 （中文）.
- ^ David A.Grossman，Ophir Frieder，“信息检索：算法和启发式”，2004年第2版，ISBN 1402030045
- ^ Kleene（斯蒂芬·科尔·克莱尼）1943 in Davis 1965:274
- ^ Rosser（巴克利·罗瑟）1939 in Davis 1965:225
- ^ 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）.
- ^ 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）.
- ^ "Any classical mathematical algorithm, for example, can be described in a finite number of English words"（Rogers 1987:2）.
- ^ "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 use of continuous methods or analogue devices... carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2）.
- ^ 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）.
- ^ Ada Lovelace honoured by Google doodle. The Guardian. 10 December 2012 [10 December 2012]. （原始内容存档于2018-12-25）.
- ^ 2.4 赛场统分. 读书频道-IT技术图书-51CTO.COM. [2017-06-07]. （原始内容存档于2017-03-24）.
- ^ 实验3-9：循环打擂. 湖南科技大学程序设计在线评测（Online Judge）.[永久失效链接]
- ^ 高中,算法与程序设计,教案. 在点网. [2017-06-07]. （原始内容存档于2019-06-03）.
- ^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David. Knapsack Problems | Hans Kellerer | Springer. Springer. 2004 [September 19, 2017]. ISBN 978-3-540-40286-2. doi:10.1007/978-3-540-24777-7. （原始内容存档于October 18, 2017） （英语）.Kellerer, Hans; Pferschy, Ulrich; Pisinger, David （2004）. Knapsack Problems | Hans Kellerer | Springer （页面存档备份，存于互联网档案馆）. Springer. doi:10.1007/978-3-540-24777-7. ISBN 978-3-540-40286-2. S2CID 28836720. Archived from the original on October 18, 2017. Retrieved September 19, 2017.
- ^ For instance, the volume of a convex polytope （described using a membership oracle） can be approximated to high accuracy by a randomized polynomial time algorithm, but not by a deterministic one: see Dyer, Martin; Frieze, Alan; Kannan, Ravi. A Random Polynomial-time Algorithm for Approximating the Volume of Convex Bodies. J. ACM. January 1991, 38 (1): 1–17. CiteSeerX 10.1.1.145.4600
. S2CID 13268711. doi:10.1145/102782.102783.Dyer, Martin; Frieze, Alan; Kannan, Ravi （January 1991）. "A Random Polynomial-time Algorithm for Approximating the Volume of Convex Bodies". J. ACM. 38 （1）: 1–17. CiteSeerX 10.1.1.145.4600 （页面存档备份，存于互联网档案馆）. doi:10.1145/102782.102783. S2CID 13268711.
- ^ George B. Dantzig and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag.
- ^ Tsypkin. Adaptation and learning in automatic systems. Academic Press. 1971: 54. ISBN 978-0-08-095582-7.Tsypkin （1971）. Adaptation and learning in automatic systems. Academic Press. p. 54. 国际标准书号 978-0-08-095582-7.
参考书目
编辑- 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此书中有列出许多相关的论文，包括哥德尔、邱奇、图灵、巴克利·罗瑟、斯蒂芬·科尔·克莱尼及埃米尔·波斯特的论文。在参考文献中也会列出原作者的姓名。
参阅
编辑
.gif){kind=small}
延伸阅读
编辑[编]
