算法(algorithm)是指在解决问题时,按照某种机械的步骤一定可以得到问题的结果(有解时给出问题的解,无解时给出无解的结论)的处理过程。当面临某个问题时,需要找到用计算机解决这个问题的方法和步骤,算法就是解决这个问题的方法和步骤的描述。
所谓机械步骤,是指算法中有待执行的运算和操作,必须是相当基本的。换言之,它们都是能够精确地被计算机运行的算法,执行者(计算机)甚至不需要掌握算法的含义,即可根据该算法的每一个步骤进行操作并最终得出正确的结果。
“算法”其实并不是一个陌生的词,因为从小学大家就开始接触算法。例如运行四则运算,必须按照一定的算法步骤一步一步地做。“先运算括号内再运算括号外,先乘除后加减”可以说是四则运算的算法。以后学习的指数运算、矩阵运算和其他代数运算的运算规则都是一种算法。
就本课程而言,算法就是计算机解决问题的过程。在这个过程中,无论是形成解决问题的思路还是编写算法,都是在实施某种算法。前者是推理实现的算法,后者是操作实现的算法。
算法由操作、控制结构、数据结构3 要素组成。
算法实现平台尽管有许多种类,它们的函数库、类库也有较大差异,但必须具备的基本操作功能是相同的。这些操作包括以下几个方面:
算术运算:加、减、乘、除。
关系比较:大于、小于、等于、不等于。
逻辑运算:与、或、非。
数据传送:输入、输出、赋值(计算)。
一个算法功能的实现不仅取决于所选用的操作,还取决于各操作之间的执行顺序,即控制结构。算法的控制结构给出了算法的框架,决定了各操作的执行次序。这些结构包括以下几个方面:
顺序结构:各操作是依次进行的。
选择结构:由条件是否成立来决定选择执行。
循环结构:有些操作要重复执行,直到满足某个条件时才结束,这种控制结构也称为重复或迭代结构。
算法操作的对象是数据,数据间的逻辑关系、数据的存储方式及处理方式即是数据结构。它与算法设计是紧密相关的。在后面的具体案例分析讲解中会进行描述。
并不是所有问题都有解决的方法,也不是所有解决问题的方法都能设计出相应的算法。算法必须满足以下5 个重要特性。
一个算法在执行有穷步骤之后必须结束,也就是说,一个算法它所包含的计算步骤是有限的,即算法中的每个步骤都能在有限时间内完成。
对于每种情况下所应执行的操作,在算法中都有确切的规定,使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下,算法都只有一条执行路径。
算法中描述的操作都可以通过已经实现的基本操作运算有限次地实现。
有输入作为算法加工对象的数据,通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入,而有的算法表面上可以没有输入,实际上已被嵌入算法之中。
它是一组与输入有确定关系的量值,是算法进行信息加工后得到的结果。