算法

来自计算思维百科
跳转至: 导航搜索

算法是对特定问题求解步骤的一种描述。

基本概念

算法是对特定问题求解步骤的一种描述。例如,计算机用于解决数值计算,如科学计算中的数值积分、解线性方程等计算方法,就是数值计算的算法。用于解决非数值计算,如用于管理、文字处理、图像图形等的排序、分类和查找,就是非数值计算的算法。尽管算法并不给出问题的精确解,只是说明怎样才能得到解。但是,算法是由有限个操作组成,这些操作包括加、减、乘、除和判断等,并按顺序、分支、循环等结构组织在一起。

算法起源

“算法”在中国古代文献中称为“术”或者“算术”,最早出现于《周髀算经》、《九章算术》等。《周髀算经》的成书年代虽至今未确认,但它是中国历史上最早一本算术类经书。《九章算术》也是现存最早的中国古代数学著作之一,其中给出了如四则运算、最大公约数、最小公倍数、开平方根、开立方根、线性方程组求解的算法等。三国时代数学家刘徽给出的求圆周率算法—刘徽割圆术,也是中国古代算法一大代表作。

“算法”一词的出现,始于唐代。当时就有《一位算法》、《算法》等专著。以后历代更有很多“算法”专著,最有代表性的是宋代数学家杨辉的《杨辉算法》。

英文名称“Algorithm”是从公元9世纪古代阿拉伯数学家阿科瓦里茨米(Abū ʿAbd Allāh Muḥammad ibn Mūsa al-Khwārizmī)的名字派生演变而来的。从他的名字“Al-Khwārizmī”派生出了“Algorism”,至18世纪演变为“Algorithm”。另外,代数的英文“Algebra”是从“al-jabr”派生出来的,后者是阿科瓦里茨米用于解二次方程的两个运算操作之一。

一般认为,历史上第一个算法是欧几里得算法,即辗转相除法。欧几里得算法最早出现于公元前3世纪欧几里得所著的《几何原本》,该算法用于求解两个正整数的最大公约数,直到现在还经常使用。

特征

  1. 确定性(Definiteness):算法的每一个步骤,都有精确的定义。要执行的每一个动作都是清晰的、无歧义的。
  2. 有穷性(Finiteness):算法必须在有限步骤内终止。
  3. 输入(Input):一个算法有0个或多个输入,作为算法开始执行的初始值,或初始状态。
  4. 输出(Output):一个算法必须有一个或多个输出,也就是算法的计算结果。输出与输入有特定关系,不同取值的输入,产生不同结果的输出。
  5. 可行性(Effectiveness):算法中所描述的运算和操作必须是可以通过有限次基本运算来实现的。

算法质量

算法是为解决一个特定的问题所采取的确定的有限步骤。它告诉计算机如何一步一步地进行计算,直至解决问题。对于一个给定的问题,可能有多个算法,但它们的质量不会完全相同。衡量算法质量的主要因素是执行时间的长短和存储空间的多少。就目前硬件而言,尤以时间因素为贵。当然还有其他的质量因素,如收敛速度的快慢、误差积累的大小以及结果精度的高低等等。

算法组成

算法是由一些操作和数据组成,而这些操作又是按照一定的控制结构所规定的次序执行。因此,算法是由数据、操作和控制结构三要素组成。

数据

数据是指操作对象和操作结果。由于算法层出不穷,变化万千,其操作对象数据和操作结果数据名目繁多,不胜枚举。最基本的有布尔值、字符、整数和实数等;稍复杂的有向量、矩阵和记录等;更复杂的有集合、树和图,还有声音、图形和图像等。

操作

算法中的每一步都能分解成计算机的基本操作,否则算法是不可行的。算法的操作种类也是五花八门、多姿多彩。最基本的有赋值运算、算术运算、逻辑运算和关系运算等;稍复杂的有算术表达式和逻辑表达式等;更复杂的有函数值计算、向量运算、矩阵运算、集合运算,以及表、栈、队列、树和图的运算等;此外,还可能有以上列举的运算的复合和嵌套。

控制

算法的控制结构给出了算法的框架,决定了各种操作的执行次序。任何复杂的算法都可以用顺序结构、分支结构和循环结构三种控制结构组合而成。

算法与计算

问题的求解是计算,求解算法中的每一步骤也是计算。计算的过程是算法,算法又由计算步骤构成。计算的目的由算法实现,算法的执行由计算完成。算法是计算科学中最重要的内容,有的专家甚至称:计算机科学就是算法的科学。

应用案例

应用1-生活中的算法

案例:上司拿了一沓客户资料给下属,让下属将这些客户资料按照客户姓氏首字母排列好。

解决步骤:

案例中下属排列客户资料的一系列步骤就称为“算法”。客户资料就是算法中的“输入项”,排列好的客户资料就是算法中的“输出项”。 下属排列客户资料的步骤肯定是有限的并且每一步都是确定的可以实现的,体现算法的“有穷性”和“确切性”。到最后下属肯定能把资料排列好体现算法的“可行性”。

应用2-计算机中的算法

顺序查找算法:在4 5 2 8 0 9 中找出数字2。

解决步骤:

第一步:将4与2比较,判断不相等,进行下一步; 第二步:将5与2比较,判断不相等,进行下一步; 第三步:将2与2比较,判断相等,输出2,结束。

在这个案例中,算法执行三步就结束了,并且算法最多执行6次,所以算法是“有穷的”。算法的每一步都是清晰确定的,所以算法是“确切的”。算法执行三步确实可以找到2,所以算法是“可行的”。4 5 2 8 0 9 是算法的输入项,2是算法的输出项。

可以体现的计算思维

抽象是从各种各样的事物中抽取出共同的、本质性的特征,舍弃其非本质的特征。例如将各种解决问题的方法的共同特征提取出来就成了“算法”。抽象能力要求能够从纷繁复杂的事物中提炼本质的过程,是一个具体到概念的过程。“算法”这一概念的提出体现计算思维中的“抽象”特点。