算法
算法（Algorithm）是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，能够得出所要求或期望的终止状态或输出数据。
算法常常含有重复的步骤和一些比较或逻辑判断。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
目录 |
[编辑] 历史
算法在中国古代文献中称为“术”，最早出现在《周髀算經》、《九章算术》。特别是《九章算术》，给出四则运算、最大公约数、最小公倍数、开平方根、开立方根、求素数的埃拉托斯特尼筛法，线性方程组求解的算法。三国代的刘徽给出求圆周率的算法：刘徽割圆术。
自唐代以来，历代更有许多专门论述“算法”的专著：
- 唐代：《一位算法》 一卷，《算法》 一卷；
- 宋代：《算法绪论》 一卷、《算法秘诀》 一卷；最著名的是杨辉的《杨辉算法》；
- 元代：《丁巨算法》；
- 明代：程大位 《算法统宗》
- 清代：《开平算法》、《算法一得》、《算法全书》。
而英文名稱「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)，算法的时间复杂度也因此记做
因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐近时间复杂度（Asymptotic Time Complexity）。
[编辑] 空间复杂度
算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。
[编辑] 非確定性多項式時間（NP）
[编辑] 实现
算法不单单可以用计算机程序来实现，也可以在人工神经网络、电路或者机械设备上实现。
[编辑] 範例
[编辑] 求最大值演算法
这是算法的一个简单的例子。
我们有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数字看成是一颗豆子的大小，可以将下面的算法形象地称为「捡豆子」：
- 首先将第一颗豆子放入口袋中。
- 从第二颗豆子开始检查，如果正在检查的豆子比口袋中的还大，则将它捡起放入口袋中，同时丢掉原先口袋中的豆子。直到最后一颗豆子。
- 最后口袋中的豆子就是所有的豆子中最大的一颗。
给定：一个数列“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
- 如果M < N，则交换M和N
- M被N除，得到余数R
- 判断R＝0，正确则N即为「最大公约数”，否则下一步
- 将N赋值给M，将R赋值给N，重做第一步。
用「BASIC代码」表示——
IF M < N THEN SWAP M,N R = M MOD N DO WHILE R <> 0 M = N N = R IF M < N THEN SWAP M,N R = M MOD N LOOP PRINT N
[编辑] 设计和分析的基本方法
[编辑] 分类
[编辑] 参见
|
||||||||||||||||||||||||||||||||||||||||||||
[编辑] 外部链接
