1.6.2　算法效率评价

算法执行时间需通过依据该算法编制的程序在计算机上的运行时所耗费的时间来度量，而度量一个算法在计算机上的执行时间通常有如下两种方法。

1．事后统计方法

目前计算机内部大都有计时功能，有的甚至可精确到毫秒级，不同算法的程序可通过一组或若干组相同的测试程序和数据以分辨算法的优劣。但是这种方法有两个缺陷：一是必须依据算法事先编制好程序，这通常需要花费大量的时间与精力；二是时间的长短依赖计算机硬件和软件等环境因素，有时会掩盖算法本身的优劣。因此，人们常常采用事前分析估算的方法评价算法的好坏。

2．事前分析估算方法

这主要在计算机程序编制前，对算法依据数学中的统计方法进行估算。这主要是因为算法的程序在计算机上的运行时间取决于以下因素。

（1）算法采用的策略、方法。

（2）编译产生的代码质量。

（3）问题的规模。

（4）书写的程序语言，对于同一个算法，语言级别越高，执行效率越低。

（5）机器执行指令的速度。

在以上5个因素中，算法采用不同的策略，或不同的编译系统，或不同的语言实现，或在不同的机器上运行时，效率都不相同。抛开以上因素，算法效率则可以通过问题的规模来衡量。

一个算法由控制结构（顺序、分支和循环结构）和基本语句（赋值语句、声明语句和输入输出语句）构成，则算法的运行时间取决于两者执行时间的总和，所有语句的执行次数可以作为语句的执行时间的度量。语句的重复执行次数称为语句频度。

例如，斐波那契数列的算法和语句的频度如下。

每一条语句的右端是对应语句的频度（frequency count），即语句的执行次数。上面算法总的执行次数为f（n）=1+1+1+n+4（n-1）=5n-1。