算法(翻译来自Wiki)介绍.doc

1、算法译自 From Wikipedia, the free encyclopedia一种计算在位置名为A 和 B 的两个数字（欧几里得的算法）的流程图。a 和b 的最大公约数(g.c.d.)的算法该算法通过在两个循环中连续减进行的：如果测试 BA产生的是 " 是 "（或真）（更准确地说位置 B 的数字 b 是大于或等于位置 A 的数字 a）那么，算法指定 BB- A(意思是数字 b- a 替换旧 b) 。同样，如 A>B，那么 AA- B。当 B（的内容）为 0 时进程终止，在 A 生成最大公约数（按照 Scott 2009:13 派生的算法；符号和绘图风格按照 Ta

2、usworthe1977）。在数学和计算机科学中，算法是一个计算的分步过程。算法用于计算、数据处理和自动推理。算法是一种表达成定义明确的有限指令表的一个函数的计算的有效方法。从初始状态和初始输入（可能为空）开始，指令描述当执行一个计算时通过有限数量的明确 定义的连续状态，最终产生 " 输出 " 并在最终的结束状态终止。从一种状态过渡到下一步并不是一定确定的；一些称为随机算法的算法，将随机输入纳入。尽管阿尔·克沃理滋米（ al Khwrizm ）的算法提到使用印度-阿拉伯数字进行算术的规则及线性和二次方程的系统解决方案， 但成为现代算法的一部分的公式化始于 1928

3、 年试图解决大卫·希尔伯特 （David Hilbert ）构 成的 " 决策问题 " (Entscheidungsproblem ）。随后的公式化被构架成试图定义 " 有效的计算 " 或 " 有效的方法 " ；这些公式化包括 1930 年、1934 年和 1935 年的高德尔 - 赫尔布兰德 - 克林（ G?delHerbrand Kleene ）的递归函数， 1936 年的阿隆索·丘尔奇（Alonzo Church）的 演算 、1936 年的爱米尔·泊思特 （Emil Post ）的 " 公

4、式 1" 和 19367 和 1939 年的阿兰·图灵的图灵机。给予算法一个正式的定义，对应的直观的概念仍然是一个具有挑战性的问题。1 非正式定义围绕算法的定义的各种观点的详细介绍，请参考算法特征化。以详细方式指定的简单的加法算法的示例在算法的特征化中描述的有， 请参见算法的例子虽然没有普遍接受的 " 算法 " 的正式定义，但非正式的定义可能是 " 精确地定义一个序列的一组规则 " ，其中会包括所有的计算机程序， 包括不执行数值计算的程 序。对一些人来说， 程序只是一种算法， 如果它最终停止的话。对另一些人来讲，程序只是一种算法，如果

5、它执行了许多计算步骤的话。算法的一个典型的例子是欧几里得的确定两个整数的最大公约数的算法；一个（有其它的）由上述流程图描述的示例并在后节中作为例子。布劳思 &杰弗里（ Boolos& Jeffrey ，1974 年、 1999 年）在以下引文中提供字的一个非正式的意思：不会有任何人用一些记数法可以写得足够快或足够长或足够小 ?(?" 无限的越来越小 . 你会试图在分子、 原子、电子上写 ") 来列出可数的无限集的所 有成员，写出它们的名字，一个接一个。但人可以做点同样有用的某些事，在某些可数无限集的情况下： 他们可以给显式指令来确定集的任意有限的 n 的第

6、n 个成 员。这种指令是非常明确地给予的，以一种它们可以被计算机或被一个能够履行对符号进行非常初级操作的人遵循的形式。" 可数的无限 " 一词意味着 " 用整数或许能扩展到无穷大的数数" 。因此， 布劳思 &杰弗里说算法意味着从一个任意的 " 输入 " 整数或数个整数， 理论上可 以从 0 到无穷大选择来 " 创造 " 输出整数的过程。因而算法可以是如 y=m+n- 两个任意 " 输入变量 "m和 n 产生输出 y 的代数方程。但众多的作者试 图界定表明这个词意味着比这更多的东西的概念，

7、关于次序（对求和的例） ：为指定的 " 计算机 " （机器或人类，配有必要的内部信息和能力）搜索、解码然后处理任意输入的整数 / 符号 m和 n、符号 +和=. 并在 " 合理的 " 时间内 " 有 效地 " 以指定的格式在指定的地点产生输出整数 y 制定的 " 移动 " 的快速、高效、 " 良好 " 的进程的精确指令 (" 计算机 " 理解的语言 ) 。算法的概念也用于定义可判定性的概念。这一概念是解释正式系统怎样从一小套的公理和规则开始进入的的中心。 在逻辑中，算法需要完

8、成的时间不能测量，因为它 显然不与我们习惯的物理维度相关。从这种不确定性上特征化进行着工作，阻止既适合具体（在某种意义上 ) 又适合这一术语的抽象用法的算法的定义的不可利用 性。2 公式化算法是计算机处理数据的必不可少的方式。许多计算机程序包含计算机应执行 （按特定的顺序） 的详细的特别的指定任务的算法，如计算雇员的薪水或打印学生的报告卡。因此，算法可以被认为是一种任何能通过完备图灵系统模拟的操作序列。 断言这个的论文作者包括明斯基(Minsky ，1967) 、萨瓦奇 （ Savage ， 1987 年）和古列维奇（ Gurevich ，2000 年）：明斯基： " 但是，我们也将

9、保持， 用图灵 .任何能 " 自然地 "被称为是有效的过程其实可以由（简单）的机器实现。虽然这可能看起来极端，但 .对其有利的论点很难反驳" 。古列维奇：".有利于他的论文的图灵非正式理由判明了更强的论题：每一种算法通过图灵机可以模拟的.根据萨瓦奇1987年 ，算法是一个由图灵机定义的计算过程" 。通常，当算法相连于处理信息时 , 关联数据是从一个输入源中读取、写到输出设备上的， 存储进行进一步处理。 存储的数据被认为是执行算法的实体的内部状态的一部分。在实践中，状态存储在一个或多个数据结构中。对于一些此类计算的过程，必须严格定义算法：指定它适

10、用于所有可能的情况下可能出现的方式。 就是任何条件的步骤必须有系统地处理， 每种情况的；每个情况的标准必须是明确的（和可计算的）。因为算法是精确的确切步骤列表，计算的顺序总是算法运作的关键。指令通常被假定为显式地列出，被描述为 " 从顶部 " 开始和进行 " 到底部 " ，更正式的由控制流描述的想法。到目前为止，这种算法的公式化讨论已假定了命令式编程的前提。这是最常见的构想，它会尝试以离散的、 " 机械的 " 手段描述一个任务。独有的这个公式化算法的构想是赋值操作，设置变量的值。它源于作为便笺簿的 " 记忆 " 的

11、直觉。下面有一个这种赋值的例子。对是什么构成一种算法的某些替代构想请参阅功能编程和逻辑编程。21算法表示算法可以表示成许多种类的符号，包括自然语言、伪代码、流程图、 drakon 图（俄罗斯的算法可视化编程语言）、编程语言或控制表 （由编译器处理 ) 来表示。算法的自然语言表达式往往是冗长和含糊不清的，很少用于复杂的或技术的算法。伪代码、流程图、 drakon 图和控制表是表达算法 的结构化方式，避免自然语言语句中很多常见的含糊之处。 编程语言主要是以一台计算机能执行的形式表达算法，但常常作为一种定义或文件的算法的方式来用。有多种可能的表达和人们可以把给定的图灵机程序表达成机器表（更多看有限状

12、态机、状态转换表、控制表）的一个序列，表达成流程图和 drakon- 图（更多看状态图），或表达成最基本的机器代码或称为 " 四节集 " 的汇编代码（更多看图灵机）。算法的表示形式可以分为图灵机说明的三个接受级别：1 高级别描述： ".用来描述一种算法的语句，忽略详细信息的实现。在这一级我们不需要陈述这台机器是如何管理其磁带或头的" 。2 执行描述： ".用来定义图灵机使用它的头和它在其磁带上存储数据的方式的语句。 在这一级我们不给出状态或转换功能的详细信息" 。3 公式描述：最详细的 " 最低级 " ，给予图灵机

13、的 " 状态表 " 。3 执行大多数算法旨在作为计算机程序执行。不过，算法也有其它执行手段，如在生物神经网络 ( 例如，人类的大脑执行算术运算或昆虫寻找食物 ) 、在电气电路或在机械装置中。4 计算机算法规范的包姆 - 牙克比尼（ B?hm Jacopini ）结构的流程图示例： SEQUENCE（序列：页上降序的矩形） 、WHILE-DO和 IF-THEN-ELSE。三个结构构成原始条件的 GOTO （如果测试 = true 然后 GOTO到步骤 xxx ）（一个钻石），无条件地 GOTO（矩形）、各种赋值运算符（矩形）和 HALT （停止，矩形）。在分配块内部嵌套这些结

14、构造成复杂的图 ( 参考 Tausworthe 1977:100 114) 。在计算机系统中，一种算法基本上是编写软件的软件开发人员在程序中写的从给定的输入（可能为 null ）有效地为要生成输出的目标机预定的 " 目标 " 计算机的逻辑的一个实例。" 优雅 " （简洁）的程序、 " 良好 "( 快速 ) 的程序： 非正式地出现在克努思（ Knuth）和精确的柴厅（ Chaitin ）的 " 简洁和优雅 " 的概念：克努思 : 我们要的是某些松散定义的审美意义上的良好算法。个标准 . 是执行算法所需的时间的长度。

15、另一个标准是算法对计算机的适应性，其简洁和优雅，等 " 。一柴厅：".一个程序是优雅的， 我是说它是生产它的输出的最小可能程序 " 。柴厅在定义前的前言： " 我会让你看你不能证明一个程序是优雅的 "-这样的证明应解决停止问题( 同上 ) 。算法对算法可计算的函数：对于给定的一个函数可能存在多个算法。这是真的，甚至程序员不用扩大程序员可用的指令集。罗杰斯（ Rogers）观察到 " 这对 . 区分算法的概念即过程和算法可计算的函数的概念即映射过程产生的来说是重要的。相同的函数可能有几种不同的算法" 。不幸的是优良 ( 速度

16、) 和优雅 ( 简洁度 ) 之间可能会有权衡的-优雅的程序可能比一个不太优雅的完成一个计算需要更多的步骤。一个使用欧几里德的算法示例显示在下方。计算的计算机（计算者）、模型： 计算机（或人类 " 计算者 " ）是一种 受限制的类型的机器， 一种盲目地跟随它的指令的 " 离散的确定性的机械装置 " 。摩尔扎克（ Melzak）和兰姆别克（ Lambek）的原始模型把这种概念减 少到四个要素： (i) 离散的、可区分的位置； (ii) 离散的、难以区分的计数器；(iii) 代理； (iv) 有效的说明代理的能力的指令列表。明斯基在他的 " 可计算性

17、的非常简单的基础 " 中描述更为合意的兰姆别 克的 " 算盘 " 模型的变型。明斯基的机器通过其五个指令（或六个，看人怎样计数）按顺序进行除非一个有条件的 IF THEN GOTO或一个无条件地 GOTO 更改顺序的程序流。除了 HALT（停止），明斯基的机器包括三个赋值（替换，代替）操作： ZERO（零） （既位置的内容替换为 0：L0) ， SUCCESSOR（后续者） ( 既 LL+1)和 DECREMENT（减） ( 既 LL- 1) 。很少有程序员写这种有限的指令集的 " 代码 " 。但明斯基证明（ Melzak 和 Lambek同样

18、）他的机器是只有四种一般指令类型的图灵完整的：有条件的 GOTO，无条件的 GOTO、分配 / 更换 / 替代和停止。一种算法的仿真：计算机（计算者）语言： 克努思劝告读者 " 学习算法 的最佳方法是尝试它 . 立即带笔和纸和通过一个例子来 " 。但关于真实的东西的模拟或执行呢？程序员必须把算法翻译成模拟器 / 计算机 / 计算者能够有 效地执行的一种语言。思通（ Stone）给了一个这样的例子：当计算二次方程根时计算机必须知道怎样取一个平方根。 如果它们不的话那么算法必须提供一套能 够有效提取一个平方根的规则。这意味着程序员必须知道相对于目标计算代理 ( 计算机 / 计算

19、者）的有效的 " 语言 " 。但模拟应使用哪种模型呢？范·爱姆德·包阿思（ Van Emde Boas）指出 " 即使我们把复杂性理论基于代替具体的机器的抽象上，选择模型的任意性依然的。此时是仿真的概念进入的时候 " 。当要测量速度时 , 指令集要参入。例如，在欧几里德的计算余数的算法子程序中执行将快得多如果程序员有一个可用的 " 模 " （除）指令而不是只是减（或者更糟：只是明斯基的 " 减") 。结构化编程、规范的结构：每一丘尔奇 - 图 灵议题由已知的图灵完整机模型任何算法可以计算的，每一

20、明思基的图灵完整性的证明只要求有四个指令类型 -有条件 GOTO、无条件 GOTO、assignment （分配）和 HALT（停）。凯梅尼 (Kemeny)和库尔茨 (Kurtz) 观察到在 " 无纪律 " 的使用无条件 GOTOs和有条件的 IF-THEN GOTOs可导致 " 意粉代码 " 时程序员可以使用这些指令写结构化的程序；另一方面 " 也可能是并不太难的，以一种结构化的语言写糟糕的结构化程序 " 。陶思沃 瑟（Tausworthe ）补充了三个包姆 - 牙克比尼规范结构： SEQUENCE,IF-THEN-ELSE, 和

21、 WHILE-DO，另有两个： DO-WHILE和 CASE。结构化的另一个好处是它本身是使用数学归纳法的正确性的证明。规范流程图符号： 称为流程图的图形助手提供一种算法（一种计算机的程序）的描述和文档的方法。像明斯基机器的程序流一样，流程图总是从一个页面的顶部开始和向下进行。其主要符号只有4 个：显示程序流的方向的箭头，矩形 (SEQUENCE,GOTO)、钻石（ IF-THEN-ELSE）和点 (OR并列 ) 。包姆- 牙克比尼规范结构是由这些原始形状构成的。分结构可以 " 住在 " 矩形中但其必须是一 个上层建筑发生的退出（ exit ）。符号和使用它们生成的规范结构

22、在图中显示。5 算法例子随机值的数组的快速排序算法的动画。红色棒标记数据中心元素；在动画开始时，右手边最远的元素选择作为数据中心。一个最简单的算法是找到列表数字（未排序）中的最大数。解决方案需要一定看列表中的每个数， 但每个只一次。此后跟随一个简单的算法，可以用高级别描述英语文句陈述：51高级别描述：1 假设第一项最大。2 看看列表中每个剩余的项， 如果它大于到目前为止的最大项，记下它。3 当过程完成后列表中标记的最后一个项是最大的项。( 准-) 正式描述： 写文句但更接近于计算机程序的高级别语言，以下是更正式编码的算法的伪代码或洋泾浜的代码：AlgorithmLargestNumberInp

23、ut: A non-empty list of numbersL.Output: Thelargestnumber in the listL.largest L0for each item in the list(Length(L) 1) ,doifthe item > largest,thenlargest the itemreturn largest" " 是 " 更改成 " 的简写形式。例如， " 最大 项 " 意味着最大项的值更改成项的值。" return " 终止算法和输出之后的值。52欧几里德算法

24、1908 年的添加更多细节的希思（T.L.Heath）的欧几里德的算法示例图。欧几里德并没有超越第三次测量，没有举例说明数值。尼克玛克思（ Nicomachus）给出了 49 和 21 的示例： " 我从最大的减小的；剩下28; 然后我再从中减去这同一的21（这是可能的）；剩下7；我从 21 减去这个，剩下14; 从中我再减去 7（这是可能的）；剩下7，但不能从 7 减去 7" 。希思评论说：" 最后一句很好奇， 但它的意义是明显够的， 一样句子关于 ' 在一个同一的数字 ' 结束的意思也是明显够的。 ( 希思 1908:300) 。欧几里德的算法

25、出现在他的 元素的书 VII(" 基本数字理论 ) 中的命题 II 。 欧几里德带来了一个问题： " 鉴于两个数字彼此不能互为质数，来找它们最大的共同度量 " 。他定义 " 应该 一个数字是由众多的单位组成的 " ：一个可数的数， 一个不包括 0 的正整数。来 " 度量 " 是放置一个较短的度量长度 s(q倍 ) 连续沿更长长度 l 直到剩余部分 r 小于较短的长度 s。用现代的话说，余数 r=l - q*s ，q 是商数或余数 r 是 " 模 " ，除后留下的整数小数部分。欧几里得的方法要想成功，起始长

26、度必须满足两个要求： (i) 长度必须不是 0， (ii) 减法必须是 " 恰当的 " ，测试必须保证两个数字中较小的从较大的减去（或者，两个可以相等它们减将产生 0）。欧几里德的原始证明添加了第三个：两个长度彼此不是互为质数的。欧几里得这样规定使得他可以构造反证法证明这两个数字的共同度量事实是最大的的。而尼克玛 克思的算法与欧几里德的是相同的，当数字彼此互为质数时产生它们共同的度量为数字 "1" 。所以要精确以下是尼克玛克思的算法。使用 1599 和 650 的欧几里德的算法的图形表达例。1599 = 650*2 + 299650 = 299*2 +

27、52299 = 52*5 + 3952 = 39*1 + 1339=13*3+0521欧几里德算法的计算机语言执行欧几里得的算法只需几个指令类型-一些逻辑测试（有条件 GOTO），无条件 GOTO、分配 ( 替换 ) 和减法。位置由大写字母符号表征，如S ，A等。一个位置中的变化量（数字）以小写字母写并与该位置的名称（通常）相关。例如，开始时的位置L 可能包含数字 l=3009 。522非优雅的欧几里得算法的程序" 非优雅 " 是一个克奴思使用的基于减法的余数 - 循环替换他的除（或 " 模" 指令）算法版本的翻译。从克奴思1973:24 派生的。根据这

28、两个数字" 非优雅 " 可能会比 " 优雅 " 用在较少的步骤计算 g.c.d. 。下面的算法构架成克奴思的欧几里得和尼克玛克思的4 步版本，但不是用除找其余数，它使用较短的长度s 从剩余的长度 r 连续减直到 r小于 s。高级别描述以粗体显示，是从克奴思1973:2 4 改编的：输入：1 在两个地点 L 和 S 放表示两个长度的数字l 和 s ：INPUT L, S2 初始化 R：使剩余的长度r 等于开始 / 初始 / 输入长度 l:R LE0: 确保 r s3 确保两个数字中较小的在S 和较大的在 R：IFR>STHENL 的内容是较大的数所以

29、跳过交换步骤4、5和6：GOTO step 6ELSE交换 R和 S 的内容。4 L R（这第一步是冗余的，但对于后来的讨论非常有用） 。5R S6S LE1： 找余数 ：直到 R中的剩余长度 r 小于 S 中的短长度 s，重复从 R 中的剩余长度 r 减去 S 中的测量数字 s。7IFS>RTHENdone measuring so这样进行测量GOTO10ELSEmeasure again, 再测量8RR-S9Remainder-loop: 余数 - 循环 GOTO7.E2： 余数是 0? ： 或者 (i) 最后一次测量是确切的和R 中的余数是 0 程序可以停止， 或者 (ii)该算法

30、必须继续： 最后一次测量在R中留有小于S 中的测量数。10IFR=0THENdone so这样做了GOTOstep 15ELSECONTINUE TOstep 11 ,E3： 交换 s 和 r: 欧几里德算法的外壳。使用余数 r 来衡量以前较小的数字 s 是多少 :;L 作为一个临时位置。11 L R12 R S13 S L14Repeat the measuring process:重复测量过程：GOTO7OUTPUT:15 Done. S contains thegreatest common divisor:S 包含最大公约数输出：15 已做。 S 包含最大公约数 ：PRINT SDON

31、E:16 HALT, END, STOP.523优雅的欧几里得的算法程序以下欧几里得算法的版本只需要有 6 个核心指令做 " 非优雅 " 的要求 13 个做的；更糟糕的是， " 非优雅 " 的需要更多类型的指令。 " 优雅 " 的流程图可以在这篇文令LET=章的顶部发现。 在( 非结构化）的 Basic 是用符号化的分配指令。语言中步骤有编号， 指5 REMEuclid'salgorithmforgreatestcommondivisor欧几里德最大公约数算法6 PRINT "Type two integers gr

32、eater than 0"打印两个大于0 的整数10 INPUT A,B20 IF B=0 THENGOTO8030 IF A > B THENGOTO6040 LET B=B-A50GOTO2060 LET A=A-B70 GOTO2080 PRINT A90 END" 优雅的 " 怎样工作： 在 " 欧几里得循环 " 的外部位置， " 优雅的 " 在两个 " 联合循环 " 之间来来回回转移， A > B 的循环计算 A A - B，B A的循环计算B B- A。这样做是因为，当最后被减数M

33、是小于或等于减数S(差= 被减数 - 减数）时、 被减数可以成为 s（新的测量长度）和减数可以成为新的 r （要测量的长度）；换句话说反转减法运算的 " 感觉 " 。53测试欧几里得算法算法做它的作者想要它做的什么吗 ?几个测试用例通常足以确认核心功能。 一个源使用 3009 和 884。克奴思建议 40902 和 24140。另一个有趣的案例是两个相对质数数字 14157 和 5950。但特殊的例子必须查明和测试。当 R > S 、 S > R ，R = S 时"非优雅的 " 能正确执行吗 ? 对" 优雅的 " 同上：

34、B > A 、A > B ，A = B? （全是）。当一个数字是零会发生什么，两个数字都是零呢？ (" 非优雅的 " 在所有情况下永远计算； " 优雅的 " 当 A = 0 时永远计算 ) 。如果输入负数会发生什么呢？分数的数字呢？如果输入的数字即通过该算法 / 程序计算的函数域要包括仅包括零的正整数，那么在零的失败指示算 法（和实例化它的程序）是一个局部函数而不是总的函数。显著的由于例外是失败的原因的是阿丽亚娜V 火箭的失败。由使用数学归纳法证明程序的正确性： 克奴思证明数学归纳法对欧几里得算法的 " 扩展 " 版本的应

35、用，他提出 " 适用于证明任何算法的有效性的一般方法 " 。陶思沃瑟建议程序复杂性的测量是其正确性长度的证明。54测量和改进欧几里得算法优雅 ( 简洁度 ) 对良好度 ( 速度 ): 仅 6 个核心指令， " 优雅 " 明显的相比 " 非优雅 " 的 13 个指令是赢家。然而， " 非优雅 " 速度更快（它到达 HALT（停止）用较少的步骤）。算法分析表明为什 么会是这种情况： " 优雅 " 在每个减法循环中进行两个条件测试而 " 非优雅 " 只进行一次。 由于该算法（通常）

36、需要许多循环穿过，平均在做必须的余数计算后的 "B = 0?"测试上浪费许多时间。可以改进算法吗 ?：一旦程序员判定程序 " 适合 " 和" 有效 "-就是它计算的作者意欲的函数-那么问题变成了，可以改进吗？" 非优雅 " 的简洁性可以通过消除 5 个步骤来改进。但柴厅证明了压缩一个算法不能由一个广义的算法自动压缩的；相反，它仅可以试探性地，即通过穷举搜索 ( 在繁忙的海狸（ Busy beaver ）可以找到例子 ) 、试验和错误、聪明、洞察力、应用归纳推理等。观察在步骤 11、12 和 13 中重复了步骤 4、

37、 5 和 6。与 " 优雅 " 的比较提供着可以消除这些步骤和步骤 2、步骤 3 的暗示。这就减少了核心指令数目从13 到 8，这使得它的 9 个步骤比 " 优雅 " 的" 更优雅 " 。" 优雅 " 的速度可以通过把 B = 0 ？测试移出两个减法循环外改善。这个变化调用添加 3 个指令 (B = 0? ， A = 0? ，GOTO）。现在 " 优雅 " 计算示例数字更快；不管对任何给定的 A、B、R、S，这总是需要进行详细的分析的案例。6 算法分析知道对一种给定的算法理论上需要有多少特定的资

38、源（如时间或存储）常常是重要的。已开发算法分析的方法来获得这种定量的答案 （估计数）；例如，上面的排序 算法有时间条件的 o(n) ，使用大 O表示法与 n 作为列表的长度。在所有的时间算法只需要记住两个值： 目前为止发现的最大数和它在输入列表中的当前位置。因 此说有一个空间的条件 o(1) ，如果这个空间要求存储的输入数字没有被计数到，或 o(n) ，如果它计数到了。不同的算法可能会用或多或少时间、空间或比其它的 ' 努力 ' 的不同的指令集完成相同的任务。 例如，二进制搜索算法当用于表查找关于排序列表时通常优于强力顺序搜索。61正式对实证算法的研究与分析是计算机科学的学科并

39、经常不使用特定的编程语言或执行抽象地实践。 在此意义上， 算法分析类似于其它数学学科， 它集中在算法的基础属性而不 是任何特定实现的细节。通常的伪代码用于分析，因为它是最简单和最一般的表示形式。 然而，最终，大多数算法通常被实施在特定的硬件 / 软件平台上和其算法的 效率最终被使用实际的代码进行测试。对于一个 "一次性 " 问题的解决方案，特定算法的效率可能没有重大的后果（除非 n 是极大的），但对于设计用于快速交互、 商业或长生命科学用途的算法，它可能是至关重要的。频繁地从小 n 到大 n 缩放暴露低效的否则是良性的算法。实证测试非常有用，因为它可能发现意外的会影响特性的

40、相互作用。基准可用于比较程序优化后一个算法之前之后潜在的改进。611FFT 加速为了说明即使在一些极度 " 确立好的 " 算法的可能的潜在改进，最近的重大创新，与 FFT 算法（非常沉重的用于图像处理的领域）有关的，可能减少了处理时间高达 10,000 的一个因素。这个加速的影响，例如，使得便携式计算设备（以及其它设备）功耗更小。7 分类有各种方法进行算法分类，每个都有其本身的益处。71执行递归或迭代 ：递归算法是一种反复调用 （使参考）自身直到匹配特定条件，这是一种通用的函数式编程的方法。 迭代算法使用像循环一样的重复构造和有时增加如堆栈的数据结构来解决给定的问题。 有些

41、问题自然适合于一个执行或另一个执行。例如，河内塔（ towers of Hanoi ）是很好理解的递归执行。每个递归版本有一个等效 （但可能或多或少复杂的） 的迭代版本，反之亦然。逻辑：一种算法可能会被看作是受控的逻辑推演。这一概念可表示为：算法 = 逻辑 + 控制。逻辑组件表示可能会在计算中使用的公理， 控制组件确定在其中对公理采用推演的方式。 这是逻辑编程范式的基础。 在纯逻辑的编程语言中控制组件被固定， 算法由唯一逻辑组件提供指定的。这种方法呼吁的是优雅的语义：公理的改变在算法中具有定义完善的更改。串行或并行或分布式： 算 法通常讨论成假定计算机一次执行一条算法的指令。这些计算机有时称为

42、串行计算机。 为这样一种环境设计的一种算法称为串行算法，而不是并行算法或分布式的算 法。并行算法利用计算机体系结构几个处理器在同一时间可以工作在一个问题， 而分布式算法利用与网络连接的多台计算机。并行或分布式算法将问题划分为更对称 或不对称的子问题， 并一起收集回结果。 在这种算法中的资源消耗不只是每个处理器上的处理器周期， 而且也有悬挂的处理器之间通信的。 排序算法可以有效地并 行，但它们的悬挂通信是昂贵的。迭代算法一般并行的。有些问题没有并行算法，称为本质上串行问题。确定性或非确定性： 确定性算法在算法的每一步用确切决定解决问题， 而非确定性算法通过猜测解决问题尽管典型猜测使用试探法作出更

43、准确的。精确或近似： 虽然许多算法达成确切的解决办法， 近似算法寻求逼近真正的解决方案。逼近可能使用确定性或随机策略。 这种算法对许多困难问题具有实用价值的。量子算法 运行在量子计算的现实模型上。 这个术语通常用于那些好像本身是量子的算法，或用于如量子超位或量子纠缠的量子计算的一些基本特征。72设计范式算法分类的另一个方法是按其设计方法或范式。有一定数量的范例，彼此各有不同。此外，每个类别包括许多不同类型的算法。一些常见的范式包括：强力的或耗尽的搜索 。这是天真的尝试每一个可能的解决办法， 确定哪个是最佳方法。分而治之 。 分而治之算法一再降低同样的问题（通常以递归方式）到一个或多个较小的实例

44、直到实例都足够小可以容易地解决为止。 一个这样的分而治之的例子是合并排序。在 把数据划分成段后对每个数据段排序，整个数据排序可以通过合并段的排序获得。 一个更简单的分而治之的变形称为减而治之算法，解决完全相同的子问题并使用这 个子问题的解决方案来解决更大的问题。 分而治之把问题划分成多个子问题， 所以征服阶段就比减而治之的算法更复杂。减而治之算法的一个例子是二进制搜索算法。动态编程。当一个问题显示最优子结构时， 意味着解决问题的最佳方法可以从子问题的最优解构造， 重叠子问题意味着相同的子问题用来解决许多不同的问题例，更快的方法称为动态编程可以避免已经计算过的重复计算的解决方案。例如，福罗依德

45、- 瓦尔沙尔 （Floyd Warshall ）算法，从加权图中的一个顶点到一个目标的最短路径可通过使用所有相邻顶点到目标的最短路径找到。动态编程和函数结果备忘录（ memoization ：turning the results of a function into something to be remembered）走 到一起的。动态编程和分而治之之间的主要区别是在分而治之中子问题更多或更少是独立的， 而在动态编程中子问题重叠的。 动态编程和直接递归之间的区别是递归 调用在缓存或函数结果备忘录中的。当子问题是独立的且没有重复时，函数结果备忘录没有帮助； 因此动态编程不是所有复杂问题的解决

46、方案。通过使用函数结果备 忘录或维护一个子问题的表已经解决，动态编程降低多项式复数的许多指数性质的问题。贪婪的方法 。贪 婪算法类似于一种动态编程算法，但不同的是子问题的解决办法不必在每个阶段都知道； 用一个 " 贪婪 " 的选择可以做到此时什么看起来最好。贪婪方法基于当前局 部最优算法和前一阶段做的最好的决定（并不是所有可能的决定） 之上在算法阶段用最佳可能的决定 （并不是所有可行的决定）延伸解决方案。它不是耗尽的并且对 很多的问题不给一个准确的答案。 但当它工作时， 它是最快的方法。 最受欢迎的贪婪算法就是找到哈夫曼树（ Huffman Tree ）、克拉思卡尔（ Kr

47、uskal ）、普里木（ Prim）、索林（ Sollin ）给定的最小生成树。线性（编程）规划 。 当使用线性编程解决问题时，发现了输入涉及的特别不等性，然后尝试最大化 （或最小化）输入的一些线性函数。很多问题 ( 如定向图的最大流 ) 可以以线性的编程方式表示，然后由 ' 通用 ' 的算法，如辛普莱（单纯形）算法解决。线性规划 问题的一个更复杂变形称为整数编程，其中解决方案空间被限制为整数。还原。这项技术涉及通过将困难 的问题转换为更好地我们知道有（希望如此）渐近最优算法的问题来解决这个困难的问题。 目标是要找到一种还原算法其复杂性不被此还原的算法所支配。例如，在 涉及第一

48、排序的列表 （昂贵的部分） 的未排序的列表中查找中位数， 然后在排序的列表 （廉价部分）中拉出中间元素的选择算法。这种技术也称为变换和征服。搜索和枚举 。许多问题（例如下棋）可作为图上建模的问题。图探索算法指定围绕图形移动的规则， 对于这类问题很有用。 此类别还包括搜索算法、分支和绑定的枚举和回溯。随机的算法 就是那些做一些随机的（或伪随机）选择；对于某些问题，事实上可以证明最快的解决方案必须有一些随机性。 有两大类的这种算法 :1. 蒙特卡罗算法 高概率返回正确的答案。例如 RP（随机多项式）是那些运行在多项式时间内的子类。2. 拉斯维加斯算法 总是返回正确的答案， 但其运行的时间只是概率上

49、约束的，例如分散化。在优化问题中试探式算法不尝试找到最佳的解决方案，而是找到时间或资源都有限的近似解。它们不实用于找到完美的解决方案。这个的示例是本地搜索、禁忌搜索算法或模拟退火算法，这是一类通过随机量变化问题的解决的试探式的概率算法。 " 模拟退火 " 名称暗示加热和冷却金属实现无缺陷的冶金术语的含义。随机变量的目的是找到接近全局最优的解决方案，而不是只是局部最优的，这个想法是随着该算法安定到解决方案随机元素减少。近似算法是那些额外提供一些边界错误的试探式算法。遗传算法尝试通过模仿生物的进化过程找到解决问题的办法，有一个随机突变产生连续几代的" 解决方案 &qu

50、ot; 的周期。因此，它们仿效繁殖和 " 适者生存 " 。 在遗传编程中，这种方法扩展到算法，通过把算法本身作为一种问题有关的"解决方案"。73研究范畴每个科学范畴有它自己的问题，需要高效的算法。一个范畴相关的问题经常在一起研究。一些分类的示例是搜索算法、排序算法、合并算法、数值算法、图论算法、字符串算法、计算几何算法、组合算法、医疗算法、机器学习、加密、数据压缩算法和分析技术。范畴往往相互重叠，一个范畴中的算法研究进展可能会改善那些其它的、有时完全不相关的领域。 例如，动态规划被发明在优化工业的资源消耗中，但现在用于解决很多领域的广泛范围的问题。Alg

51、oritmi de numero Indorum74 通过复杂性算法可以按它们完成所需的时间与其输入的大小相比分类。有各种各样的：一些算法以相对输入大小的线性时间完成、 一些按时间的指数量这样做或更糟的，一些从 未停止。此外，某些问题可能有多个复杂程度不同的算法，而其它问题可能没有算法或没有已知的高效算法。 也有从几个问题映射的其它的问题。所以，已经发现， 也许基于它们最佳可能的算法的复杂性更适合于把问题自身分类而不是算法的等价划分为类。波尔金 (Burgin ，2005 年，p.24) 使用放松有限步骤后确定函数计算的算法的输出的共同条件的算法的广义定义。 他将一类超级递归算法定义为 &qu

52、ot; 一种算法，它可能计算任何图灵机不可计算的函数 " ( Burgin ， 2005 年， p.107) 。这息息相关于超计算方法的研究。8 持续算法形容词 " 持续的 " 应用于 " 算法 " 一词意味着：1 一种算法对代表连续量数据进行操作，即使这种数据由离散近似表示 - 这种算法在数值分析中研究；2 一种连续操作数据的微分方程形式的算法，在模拟计算机上运行的。9 法律问题算法本身通常不是可申请专利的。在美国，单一的抽象概念、数字或信号的简单操作组成的权利并不能构成 " 过程 " （ USPTO 2006年），因此算

53、法不是可以申请专利的 ( 如在高沙尔克诉本森（ Gottschalk v. Benson）中 ) 。然而，算法的实际应用有时可申请专利。例如，在戴梦德诉叠尔（ Diamond v.Diehr ）中，简单的帮助合成橡胶固化的反馈算法的应用被认为是专利。软件的专利是极具争议性的， 有涉及算法被高度批评的专利， 特别是数据压缩算法， 如 Unisys 的 LZW专利。此外，一些加密算法有出口限制( 见加密的出口）。10 词源" 算法（ Algorithm ）" 或在某些其它书面版本中的 " 算法（ Algorism ） " 一词，来自名称 al- Khwrizm ，在古典阿拉伯语发音为Al-Khwarithmi。Al- Khwrizm ( 波斯语：?，c.780-850) 是一位波斯的数学家、天文学家、地理学家和巴格达皇宫的智慧学者，其名字的意思是 " Khwarezm的本地人 " ，Khwarezm在他的时代期间是更伟大的伊朗的一部分的一个城市，现在是在现代的乌兹别克斯坦。 约 825 年，