徐素梅

（安徽理工大学 理学院，安徽 淮南 232001）

一个算法是一个有限指令的集合。这些指令确定了解决某一问题的运算或操作程序。问题是要求回答的提问。通常有几个参数或自变量，他们的值是特定的，取自问题的定义域，问题的描述即对其参数进行描述，之处其解是满足什么性质的命题。给问题的全体参数都指定了确定的值，便得到问题的一个实例。例如“y+z=?”是加法问题，而”4+7=?”是加法实例。当然，一个问题一般可以包含多个实例。一个计算机程序即使是按照正确的算法编写的，对于一些输入来时也许是毫无用处的，因为这个程序的执行时间太长，或者程序的数据、变量等占用的存储空间太大。算法分析是指通过分析得到算法所需的时间和空间的估计量，算法的复杂度是指执行算法所需的时间和空间的量。因此，本文叙述一下算法执行所需时间的问题。

1 时间复杂性

图1

用微积分可以证明，上列函数中给每个函数都小于其对于数字的函数，即每个函数与其后数字代表的函数的比在n无限增长时趋于0.图1显示了这些函数的图像，图1中函数值的每个刻度都是它前面刻度的两倍。

1.1 时间频度

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。……