算法效率的度量

算法效率的度量

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

1、事后统计的方法。因为很多计算机内部都有计时功能，有的甚至可精确到毫秒及，不同算法的程序可通过一组或若干组相同的统计数据以分辨优劣。但这种方法有两个缺陷：一是必须先运行依据算法编制的程序;二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。因此人们常常采用另一种事前分析估算的方法。

2、事前分析估算的方法。一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：a依据的算法选用何种策略。b问题的规模，例如求100内还是1000内的素数。c书写程序的语言，对于同一个算法，实现语言的级别越高，执行效率就越底。e机器执行指令的速度。

一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题平说是基本操作的原操用，以该基本操作重复执行的次数做为算法的时间量度。