算法

算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，经过计算机程序的有限次运算，能够得出所要求或期望的终止状态或输出数据。

算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法的历史

“算法”的中文名稱出自周髀算經；而英文名稱 Algorithm 来自于9世纪波斯数学家比阿勒·霍瓦里松(阿尔·花拉子米)的名字al-Khwarizmi，因為比阿勒·霍瓦里松在数学上提出了算法这个概念。“算法”原为"algorism"，意思是阿拉伯数字的运算法则，在18世纪演变为"algorithm"。欧几里得算法被人们认为是史上第一个算法。 第一次编写程序是Ada Byron于1842年为巴贝奇分析机编写求解解伯努利方程的程序，因此Ada Byron被大多数人认为是世界上第一位程序员。因为查尔斯·巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。 因为"well-defined procedure"缺少数学上精确的定义，19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要的作用。

算法的特征

1. 输入：一个算法必须有零个或多个输入量。
2. 输出：一个算法应有一个或多个输出量，输出量是算法计算的结果。
3. 确定性：算法的描述必须无歧义，以保证算法的执行结果是确定的。
4. 有限性：算法必须在有限步骤内实现。
5. 有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

形式化算法

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

算法的复杂度

算法的时间复杂度

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

$T(n)={\mathcal {O}}(f(n))$

因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。

算法的空间复杂度

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

非確定性多項式時間(NP)

主条目：NP (複雜度)

算法的实现

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

範例

求最大值演算法

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

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

1. 首先将第一颗豆子放入口袋中。
2. 从第二颗豆子开始检查，如果正在检查的豆子比口袋中的还大，则将它捡起放入口袋中，同时丢掉原先口袋中的豆子。直到最后一颗豆子。
3. 最后口袋中的豆子就是所有的豆子中最大的一颗。

下面是一个形式算法，用近似于程式語言的虛擬碼（伪代码）表示

给定：一个数列“list"，以及数列的长度"length(list)" 
largest = list[1]
for counter = 2 to length(list):
  if list[counter] > largest:
    largest = list[counter]
print largest

符号说明:

• = 用于表示赋值。即：右边的值被赋予给左边的变量。
• List[counter]用于表示数列中的第counter项。例如：如果counter的值是5，那么List[counter]表示数列中的第5项。
• <= 用于表示“小于或等于”。

求最大公約數演算法

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

1. 如果 M < N，则交换 M 和 N
2. M 被 N 除，得到余数 R
3. 判断 R＝0，正确则 N 即为“最大公约数”，否则下一步
4. 将 N 赋值给 M，将 R 赋值给 N，重做第一步。

用“BASIC 代码”表示——

 If M < N Then Swap M,N
 Do While R <> 0
     R = M Mod N
     M = N
     N = R
 Loop
 Print N

算法设计和分析的基本方法

• 分治法
• 动态规划
• 贪心法（亦作饕餮法）

算法的分类

• 基本算法
  • 枚举
  • 搜索
    • 深度优先搜索
    • 广度优先搜索
    • 启发式搜索
    • 遗传算法
• 数据结构的算法
• 数论与代数算法
• 计算几何的算法
  • 凸包算法
• 图论的算法
  • 哈夫曼编码
  • 树的遍历
  • 最短路径算法
  • 最小生成树算法
  • 最小树形图
  • 网络流算法
  • 匹配算法
• 动态规划
• 其他
  • 数值分析
  • 加密算法
  • 排序算法
  • 检索算法
  • 随机化算法
  • 关于并行算法，请参阅并行计算一文。

参见

• 计算机科学课程列表

外部链接

• 20世纪十大算法[1]