算法：修订间差异

删除的内容添加的内容

行内

2013年3月13日 (三) 03:02的版本

在數學和計算機科學之中，算法（Algorithm）爲一個計算的具體步驟，常用於計算、數據處理和自動推理。精確而言，算法是一個表示爲有限長^[1]列表的有效方法。算法應包含清晰定義的指令^[2]用於計算函數^[3] 。

算法中的指令描述的是一個計算，當其執行時能從一個初始狀態和（可能爲空的）初始輸入開始， ^[4] 經過一系列有限 ^[5] 而清晰定義的狀態最終產生輸出 ^[6] 並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化算法在内的一些算法，包含了一些隨機輸入。 ^[7] ^[8]

形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，並在其后尝试定义有效计算性^[9]或者有效方法^[10]中成形。这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于 1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年Emil Leon Post的Formulation 1 和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義爲形式化算法的情況。^[11]

历史

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

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

唐代：《一位算法》一卷，《算法》一卷；
宋代：《算法绪论》一卷、《算法秘诀》一卷；最著名的是杨辉的《杨辉算法》；
元代：《丁巨算法》；
明代：程大位《算法统宗》
清代：《开平算法》、《算法一得》、《算法全书》。

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

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

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

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

特征

以下是Donald Knuth在他的著作The Art of Computer Programming裡對演算法下的定義：

输入：一个算法必须有零个或以上输入量。
输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。
明確性：算法的描述必须无歧义，以保证算法的實際执行结果是精確地符合要求或期望，通常要求實際執行結果是确定的。
有限性：依據圖靈的定義，一個演算法是能夠被任何圖靈完備系統模擬的一串運算，而圖靈機只有有限個狀態、有限個輸入符號和有限個轉移函數（指令）。而一些定義更規定演算法必须在有限個步骤内完成任務。
有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

基本要素

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

常用设计模式

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

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

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

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

线性规划法：

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

常用实现方法

递归方法与迭代方法：见词条

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

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

精确求解和近似求解：

形式化算法

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

复杂度

时间复杂度

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

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

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

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

空间复杂度

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

非確定性多項式時間（NP）

实现

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

範例

求最大值演算法

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

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

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

下面是一个形式算法，用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;
}

求最大公約數演算法

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

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

用「ANSI C代码」表示——

void swapi(int *x, int *y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}

int gcd(int m, int n)
{
  int r;
  if (m < n)
    swapi(&m, &n);
  r = m % n;
  while (r)
  {
    m = n;
    n = r;
    if (m < n)
      swapi(&m, &n);
    r = m % n;
  }
  return n;
}

利用if函式以及遞迴則能做出更為精簡的程式碼，更可省去交換的麻煩。

int gcd(int a,int b)
{
    if(a%b)
        return gcd(b,a%b);
    return b;
}

设计和分析的基本方法

分类

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

參考

^ "Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).
^ 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).
^ "an algorithm is a procedure for computing a function (with respect to some chosen notation for integers) . . . this limitation (to numerical functions) results in no loss of generality", (Rogers 1987:1).
^ "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).
^ 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).

外部链接

参见

Template:Link FA Template:Link GA Template:Link FA

[1] "Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).

[2] 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).

[3] "an algorithm is a procedure for computing a function (with respect to some chosen notation for integers) . . . this limitation (to numerical functions) results in no loss of generality", (Rogers 1987:1).

[4] "An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins" (Knuth 1973:5).

[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).

[6] "An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs" (Knuth 1973:5).

[7] 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).

[8] 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).

[9] Kleene 1943 in Davis 1965:274

[10] Rosser 1939 in Davis 1965:225

[11] Moschovakis, Yiannis N. What is an algorithm?. Engquist, B.; Schmid, W. (编). Mathematics Unlimited — 2001 and beyond. Springer. 2001: 919–936 (Part II).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ 第46行： / 第46行： @@
 # 有限性：依據圖靈的定義，一個演算法是能夠被任何[[圖靈完全|圖靈完備]]系統模擬的一串運算，而[[圖靈機]]-{只}-有有限個狀態、有限個輸入符號和有限個轉移函數（指令）。而一些定義更規定演算法必须在有限個步骤内完成任務。
 # 有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。
+== 基本要素 ==
+算法的核心是建立问题抽象的模型和明确求解目标，之后可以根据具体的问题选择不同的模式和方法完成算法的设计。
+=== 常用设计模式 ===
+完全遍历法 和 不完全遍历法： 在问题的解是有限离散解空间，且可以验证正确性和最优性时，最简单的算法就是把解空间的所有元素完全遍历一遍，逐个检测元素是否是我们要的解。这是最直接的算法，实现往往最简单。但是当解空间特别庞大时，这种算法很可能导致工程上无法承受的计算量。这时候可以利用不完全遍历方法——例如各种搜索法和规划法——来减少计算量。
+分治法： 把一个问题分割成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。
+[[动态规划]]法： 当问题的整体最优解就是由局部最优解组成的时候，经常采用的一种方法。详见词条。
+贪婪算法： 常见的近似求解思路。当问题的整体最优解不是（或无法证明是）由局部最优解组成，且对解的最优性没有要求的时候，可以采用的一种方法。
+线性规划法：
+简并法： 把一个问题通过逻辑或数学推理，简化成与之等价或者近似的、相对简单的模型，进而求解的方法。
+=== 常用实现方法 ===
+[[递归|递归方法]] 与 [[迭代|迭代方法]]： 见词条
+顺序计算、[[并行计算]] 和 [[分布式计算]]： 顺序计算就是把形式化算法用编程语言进行单线程序列化后执行。其余见词条。
+确定性算法 和 非确定性算法：
+精确求解 和 近似求解：
 == 形式化算法 ==