1  算法

算法(algorithm)是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：

（1）有穷性。对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。

（2）确定性。对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。

（3）可行性。算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。

（4）有输入。作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。

（5）有输出。它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。

2  算法分析

评价算法的标准很多，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。将一个算法转换成程序并在计算机上执行时，其运行所需要的时间取决于下列因素：

（1）硬件的速度。

（2）书写程序的语言。实现语言的级别越高，其执行效率就越低。

（3）编译程序所生成目标代码的质量。对于代码优化较好的编译程序其所生成的程序质量较高。

（4）问题的规模。例如，求100以内的素数与求1000以内的素数其执行时间必然是不同的。

显然，在各种因素都不能确定的情况下，很难比较出算法的执行时间。也就是说，使用执行算法的绝对时间来衡量算法的效率是不合适的。为此，可以将上述各种与计算机相关的软、硬件因素都确定下来，这样一个特定算法的运行时间的多少就只依赖于问题的规模（通常用正整数n表示），或者说它是问题规模的函数。

（1）时间复杂度

一个程序的时间复杂度（Time complexity）是指程序运行从开始到结束所需要的时间。虽然算法不是程序，不能上机运行，但是对算法性能的分析，完全可以用对程序性能的分析方法进行。

（2）空间复杂度

一个程序的空间复杂度（Space complexity）是指程序运行从开始到结束所需的存储量。

程序的一次运行是针对所求解的问题的某一特定实例而言的。例如，求解排序问题的排序算法的每次执行是对一组特定个数的元素进行排序，对该组元素的排序是排序问题的一个实例。元素个数可视为该实例的特征。