历史

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

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

唐代：《一位算法》 一卷，《算法》 一卷；

宋代：《算法绪论》 一卷、《算法秘诀》 一卷；最著名的是杨辉的《杨辉算法》；

元代：《丁巨算法》；

明代：程大位《算法统宗》

清代：《开平算法》、《算法一得》、《算法全书》。

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

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

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

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

特征

以下是高德纳在他的著作《计算机程序设计艺术》里对算法的特征归纳：

输入：一个算法必须有零个或以上输入量。

输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。

明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确地匹配要求或期望，通常要求实际运行结果是确定的。

有限性：依据图灵的定义，一个算法是能够被任何图灵完备系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务。

有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

基本要素

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

常用设计模式

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

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

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

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

线性规划法：见词条。

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

常用实现方法

递归方法与迭代方法

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

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

精确求解和近似求解

形式化算法

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

复杂度

时间复杂度

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

算法执行时间的增长率与 f(n) 的增长率正相关，称作渐近时间复杂度（Asymptotic Time Complexity），简称时间复杂度。

常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n )，立方阶O(n ),...， k次方阶O(n ),指数阶O(2 )。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

空间复杂度

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

非确定性多项式时间（）

实现

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

示例

求最大值算法

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

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

首先将第一颗豆子放入口袋中。

从第二颗豆子开始检查，如果正在检查的豆子比口袋中的还大，则将它捡起放入口袋中，同时丢掉原先口袋中的豆子。反之则继续下一颗豆子。直到最后一颗豆子。

最后口袋中的豆子就是所有的豆子中最大的一颗。

在一个for循环中，每轮循环都有新的挑战者。若挑战者胜的话，挑战者做新擂主，否则擂主卫冕。for循环结束后输出最后的擂主。

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

intmax(int*array,intsize){intmval=*array;inti;for(i=1;imval)mval=array[i];returnmval;}

求最大公约数算法

求两个自然数的最大公约数设两个变量M和N

如果M < N，则交换M和N

M被N除，得到余数R

判断R＝0，正确则N即为“最大公约数”，否则下一步

将N赋值给M，将R赋值给N，重做第一步。

用ANSI C代码表示

//交換2數voidswapi(int*x,int*y){inttmp=*x;*x=*y;*y=tmp;}intgcd(intm,intn){intr;do{if(m<n)swapi(&m,&n);r=m%n;m=n;n=r;}while(r);returnm;}

利用if函数以及递归则能做出更为精简的代码，更可省去交换的麻烦。（但是也因为递归调用，其空间复杂度提高）

intgcd(inta,intb){if(a%b)returngcd(b,a%b);returnb;}

分类

基本算法

数据结构的算法

数论与代数算法

计算几何的算法

图论的算法

动态规划

其他

参看

抽象机器

垃圾进，垃圾出

算法导论

计算理论

高级综合

参考文献

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 ） 的论文。在参考文献中也会列出原作者的姓名。

参见

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。