算法的基本概念

浏览数：27 / 时间：2015年06月08日

算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，没有二义性，同时该规则将在有限次运算后可终止。
　　1）算法的基本特征
　　（1）可行性:由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的。
　　（2）确定性:算法的设计必须是每一个步骤都有明确的定义，不允许有模糊的解释，也不能有多义性。
　　（3）有穷性:算法的有穷性，即在一定的时间是能够完成的，即算法应该在计算有限个步骤后能够正常结束。
　　（4）拥有足够的情报:算法的执行与输入的数据和提供的初始条件相关，不同的输入或初始条件会有不同的输出结果，提供准确的初始条件和数据，才能使算法正确执行。
　　2）算法的基本要素
　　一是数据对象的运算和操作，二是算法的控制结构。
　　（1）算法中对数据的运算和操作
　　算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。即算法是计算机所能够处理的操作所组成的指令序列。
　　（2）算法的控制结构
　　在算法中，操作的执行顺序又称算法的控制结构，一般的算法控制结构有三种：顺序结构、选择结构和循环结构。
　　3）算法设计的基本方法
　　（1）列举法:基本思想是，根据提出的问题，列举出所有可能的情况，并用问题中给定的条件检验哪些是满足条件的，哪些是不满足条件的。
　　（2）归纳法:基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。
　　（3）递推:是从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果。本质也是一种归纳，递推关系式通常是归纳的结果。
　　（4）递归:在解决一些复杂问题时，为了降低问题的复杂程序，通常是将问题逐层分解，最后归结为一些最简单的问题。分为直接递归和间接递归两种方法。
　　（5）减半递推技术:减半递推即将问题的规模减半，然后，重复相同的递推操作。
　　（6）回溯法:有些实际的问题很难归纳出一组简单的递推公式或直观的求解步骤，也不能使用无限的列举。