什么是算法?

什么是算法?

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。

一个算法应该具有以下五个重要的特征：

1、有穷性： 一个算法必须保证执行有限步之后结束；

2、确切性： 算法的每一步骤必须有确切的定义；

3、输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；

4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

5、可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。

通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。一个算法应该具有以下五个重要的特征： 有穷性： 一个算法必须保证执行有限步之后结束； 确切性： 算法的每一步骤必须有确切的定义； 输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件； 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。 did you knowalgorithm 一词的由来algorithm(算法)一词本身就十分有趣。初看起来，这个词好像是某人打算要写“logarithm”(对数)一词但却把头四个字母写的前后颠倒了。这个词一直到1957年之前在webster's new world dictionary(《韦氏新世界词典》)中还未出现，我们只能找到带有它的古代涵义的较老形式的“algorism”(算术)，指的是用阿拉伯数字进行算术运算的过程。在中世纪时，珠算家用算盘进行计算，而算术家用算术进行计算。中世纪之后，对这个词的起源已经拿不准了，早期的语言学家试图推断它的来历，认为它是从把algiros(费力的)+arithmos(数字)组合起来派生而成的，但另一些人则不同意这种说法，认为这个词是从“喀斯迪尔国王algor”派生而来的。最后，数学史学家发现了algorism(算术)一词的真实起源：它来源于著名的persian textbook(《波斯教科书》)的作者的名字abu ja'far mohammed ibn m??s?? al-khow??rizm （约公元前825年）——从字面上看，这个名字的意思是“ja'far 的父亲，mohammed 和m??s?? 的儿子，khow??rizm 的本地人”。khow??rizm 是前苏联xиba(基发) 的小城镇 。al-khow??rizm 写了著名的书kitab al jabr w'al-muqabala (《复原和化简的规则》)；另一个词，“algebra”(代数)，是从他的书的标题引出来的，尽管这本书实际上根本不是讲代数的。逐渐地，“algorism”的形式和意义就变得面目全非了。如牛津英语字典所说明的，这个词是由于同arithmetic(算术)相混淆而形成的错拼词。由algorism又变成algorithm。一本早期的德文数学词典 vollstandiges mathematisches lexicon (《数学大全辞典》) ，给出了algorithmus (算法)一词的如下定义：“在这个名称之下，组合了四种类型的算术计算的概念，即加法、乘法、减法、除法”。拉顶短语algorithmus infinitesimalis (无限小方法) ，在当时就用来表示leibnitz(莱布尼兹)所发明的以无限小量进行计算的微积分方法。1950年左右，algorithm一词经常地同欧几里德算法(euclid's algorithm)联系在一起。这个算法就是在欧几里德的《几何原本》(euclid's elements ,第vii卷，命题i和ii)中所阐述的求两个数的最大公约数的过程(即辗转相除法)。

一、什么是算法 算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法是问题规模n 的函数f(n)，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。时间复杂度用“O（数量级）”来表示，称为“阶”。常见的时间复杂度有： O（1）常数阶；O（log2n）对数阶；O（n）线性阶；O（n2）平方阶。 算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。 [font class="Apple-style-span" id="bks_etfhxykd"]算法 Algorithm [/font] 算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。 一个算法应该具有以下五个重要的特征： 1、有穷性： 一个算法必须保证执行有限步之后结束； 2、确切性： 算法的每一步骤必须有确切的定义； 3、输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件； 4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 5、可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。 算法的设计要求 1）正确性（Correctness） 有4个层次： A．程序不含语法错误； B．程序对几组输入数据能够得出满足规格要求的结果； C．程序对精心选择的、典型的、苛刻的、带有刁难性的几组输入数据能够得出满足规格要求的结果； D．程序对一切合法的输入数据都能产生满足规格要求的结果。 2）可读性（Readability） 算法的第一目的是为了阅读和交流； 可读性有助于对算法的理解； 可读性有助于对算法的调试和修改。 3）高效率与低存储量 处理速度快；存储容量小 时间和空间是矛盾的、实际问题的求解往往是求得时间和空间的统一、折中。 算法的描述 算法的描述方式（常用的） 算法描述 自然语言 流程图 特定的表示算法的图形符号 伪语言 包括程序设计语言的三大基本结构及自然语言的一种语言 类语言 类似高级语言的语言，例如，类PASCAL、类C语言。 算法的评价 算法评价的标准：时间复杂度和空间复杂度。 1）时间复杂度 指在计算机上运行该算法所花费的时间。用“O（数量级）”来表示，称为“阶”。 常见的时间复杂度有： O（1）常数阶；O（logn）对数阶；O（n）线性阶；O（n＾2）平方阶 2）空间复杂度 指算法在计算机上运行所占用的存储空间。度量同时间复杂度。 时间复杂度举例 （a） X：=X+1 ； O（1） （b） FOR I：=1 TO n DO X：= X+1； O（n） （c） FOR I：= 1 TO n DO FOR J：= 1 TO n DO X：= X+1； O（n＾2） “算法”一词最早来自公元 9世纪 波斯数学家比阿勒·霍瓦里松的一本影响深远的著作《代数对话录》。20世纪的 英国 数学家 图灵 提出了著名的图灵论点，并抽象出了一台机器，这台机器被我们称之为 图灵机 。图灵的思想对算法的发展起到了重要的作用。 算法是 计算机 处理信息的本质，因为 计算机程序 本质上是一个算法，告诉计算机确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。 一般地，当算法在处理信息时，数据会从输入设备读取，写入输出设备，可能保存起来以供以后使用。 这是算法的一个简单的例子。 我们有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数字看成是一颗豆子的大小 可以将下面的算法形象地称为“捡豆子”： 首先将第一颗豆子（数列中的第一个数字）放入口袋中。 从第二颗豆子开始检查，直到最后一颗豆子。如果正在检查的豆子比口袋中的还大，则将它捡起放入口袋中，同时丢掉原先的豆子。 最后口袋中的豆子就是所有的豆子中最大的一颗。 下面是一个形式算法，用近似于 编程语言 的 伪代码 表示 给定：一个数列“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项。 <= 用于表示“小于或等于”。