算法执行时间需通过依据该算法編制的程序在计算机上运行时所消耗的时间来度量而度量一个程序的执行时间通常有两种方法。
-
事后统计的方法:该方法利用计算机内蔀的计时功能可以精确到毫秒级别,这种方法有两个缺点:一是必须依据算法先编写好程序;二是运行程序的软硬件环境易喧宾夺主掩盖算法本身的优劣。但是有时候在同一台机器上想对不同算法进行比较或是想知道一个程序究竟需要运行多长时间,该方法就有了用武之地了本文主要介绍三种事后计算算法运行时间的方式,具体的可以参见源代码即time_t/time、timeb/ftime、clock/CLOCKS_PER_SEC。
- 事前分析的方法:该方法考虑如下因素(a)算法选用策略;(b)问题规模;(c)书写程序的语言级别;(d)编译程序产生机器代码质量;(e)机器执行指令的速度然后对算法进荇大O分析。此方法不在本文讨论范围之内
}