程序执行时间计算

姜咏江      

简介：算法时间复杂度的研究，以所谓的多项式时间做为最低复杂度，实在有些不靠谱。计算机程序执行时间可以用其编译之后的机器语言程序来计算。因为每一机器指令（汇编指令）的指令周期都是确定的，故计算程序执行时间，可先计算出每条机器指令重复执行次数，然后与指令周期相乘求和，最终获得准确时间。本文提出的算法程序执行耗时计算，要以指令重复执行次数为基础，给出了指令重复执行次数的基本计算公式。

1.     背景

   为了研究算法程序完成任务运行时间长短，人们引入了算法时间复杂度的概念。

   在维基百科中，算法时间复杂度被定义为：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。

   在百度文库中有计算方法解释：一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f(n)，因此，算法的时间复杂度记做：T(n)=O(f(n))。若 T(n)/f(n) 求极限可得到一常数c，则时间复杂度T(n) = O(f(n))。

不论维基百科还是百度的解释，都称算法时间复杂度是程序运行时间的定量描述。实际上，我们见到的大O符号表述只能算定性描述，根本谈不上定量。

   为了能够确实对算法程序运行时间进行定量分析，本文从单处理器计算机指令设计与程序执行的原理出发，依据程序设计的基本结构，提出了一种比较切合实际的程序执行时间计算方法。结果会见到有限程序运行时间的计算，都可以表达成一种多项式形式。

2.     指令重复执行次数

   我们知道，不论任何形式的计算机设计语言程序都要转化成机器语言程序才能够执行。因此，用与机器语言一一对应的汇编语言来讨论程序执行时间才应该是最准确的。不过由于各种语言程序在执行时间分析上具有一定的一致性，故而作定性分析时，也可以替代汇编语言。

   不论何种计算机程序设计语言，就程序设计的基本结构来说都是一致的。程序的基本结构分为：顺序、分支、循环和子程序调用。任何计算机程序的执行都可以说是这几种程序结构的重复，所以计算程序执行过程所消耗的时间，都离不开对程序基本结构的分析。

   程序执行的过程是由每个指令执行的过程组成的，因而程序执行的时间就是指令执行时间的累加。在汇编程序语言中，每条指令执行的时间消耗是确定的。特别是那些指令周期相等的计算机系统设计，用单一指令执行的时间乘以全部指令重复执行的次数，就能够计算出程序执行所需要的时间。如果计算机的指令周期不相同，则可以用每条指令的指令周期做为系数，进行所谓的加权求和来计算程序执行的时间。因此，算法程序执行时间的消耗，最关键的是计算出每条指令重复执行的次数。

3.     指令重复执行次数公式

   我们将汇编程序不在执行状态的每条指令叫“写出的指令”，计算指令重复执行次数，就与这种写出的指令有关。

   指令重复执行次数是由程序的基本结构所决定的。在顺序程序结构中写出的指令重复执行次数是1。而在循环结构中，写出的指令重复执行次数与循环的次数一致。程序执行中消耗时间最长的就是循环程序结构。直观地说，循环的次数越多，处在循环体内的写出指令重复执行次数越多，因而累计耗时就越长。在此种观点之下，整个程序就可以看成是多层循环结构，可以按照多层循环结构来计算程序执行时间。当然，子程序可以单独计算子程序执行的时间。由于分支程序结构的程序分支选择总是惟一的，故时间计算基本上等同于顺序结构。

   我们将顺序与分支都认定为0层循环，那么程序运行的耗时计算，可以建立在多层循环结构的耗时计算上，也就是循环结构的写出指令重复执行次数计算上。如果用函数来描述，那么一个程序的指令重复执行次数T应为层内循环次数n与循环层数k的二元函数，即T=f(n,k)。为说明问题简单通俗，我们通过c程序的例子加以解释。

  例1，假设n=k，那么幂nⁿ结构的n重循环用c语言描述如下。

          for( i₁=1; i₀<=n; i₁++){

         for( i₂=1; i₁<=n; i₂++){

           ......

          for( i_n=1; i_n<=n; i_n++){

          no₁ += 1;

          no₂ += no₁;

          }}...}

    for语句条件表达式的初值语句在每层只执行一次，而定界和步长语句都要执行n次。显然最内层每个语句重复循环次数是nⁿ，向外各层依次为n^n-1、n^n-2、…、n²、n。那么总的语句重复执行次数为1+3n+3n²+3n³+…+3n^n-2 +3n^n-1+4nⁿ。

   对于一个程序，在顺序结构中，指令重复执行次数是1；在单层n次循环结构中，指令重复执行的次数是n；在k层n次循环当中写出的指令，其重复执行的次数是n^k。于是各层指令重复执行的次数可用公式

f(n,k) = a₀+a₁n+a₂n²+...+a_k-1n^k-1+a_kn^k                                            （1）

来计算，其中a_i是各循环层的写出指令数，i=0,1,2,...,k。

   如果将公式（1）的k认为是常量，那么（1）式不就是一个多项式吗？我们能说这种形式的算法复杂度程序执行最快吗？

4.     计算类型实例

   公式（1）中，若幂指数最高固定为常数k，则得到k次多项式；若幂底数固定为常数k，则得到指数多项式；若1层循环次数从1开始，逐层循环次数加1递增，则得到阶乘多项式。如此变化循环层数或循环次数，则可以得到各种重复执行计算的实际公式。为了说明这方面的演变，我们再举两个实例。

   例2，将（1）式的幂底数（循环次数）设定为常数2，则能够得到指数型指令重复执行的多项式表达式        

           a₀+a₁2+a₂2²+...+a_n-12^n-1+a_n2ⁿ。

   例3，设定幂底数是常数k，下面的循环结构可以实现nlog_kn型的指令重复执行次数。

for( i=0; i<n; i++){

for( j=k; j<=n; j*=k){

no₁ += 1;

no₂ += no₁;

}}

由j*=k知j的值循环变化序列为k,k²,k³,..., k^t=n，于是内层循环次数t=log_kn。

   由于这个程序的外层循环次数是n，内层循环次数是log_kn，因而程序指令重复执行次数总共是1+2n+n+4n log_kn=1+3n+4n log_kn。

5.     程序执行时间比较

   关于算法程序时间复杂度，一种流行的观点认为多项式类型的算法复杂度较低，而且认为多项式类型算法程序运行耗时最少。其实这是一种错觉。

   从公式（1）我们知道，决定算法程序执行时间长短的有两个因素，一个是多项式的幂指数k，另一个是多项式的幂底数n。当幂指数k较大的时候，虽然它是一个常数，我们也不能够认为多项式时间类型算法程序运行时间消耗会最少。特别在n<k时，从（1）式立即知道，n^k多项式型算法程序时间的消耗会大于幂nⁿ型算法程序的耗时。这说明在较大的循环层数的范围内，不能够就认为多项式时间具有较低的复杂度，当然也不能够认为这种情况的算法程序耗时最短。我们不妨仅就一项来进行比较。

   例如设n=5，k=7，那么n^k=5⁷=78125；而nⁿ=5⁵=3125。由此可见用多项式时间复杂度来说明算法程序耗时长短是不靠谱的事情。有人也许会说，n趋于无穷才对。想象一下，n趋于无穷大对程序执行的时间计算的意义有多大？

6.     结论

   计算程序执行时间，要通过程序写出的指令重复执行次数进行，指令重复执行次数的多少，取决于程序循环结构的循环次数和循环层数这两个变量。通俗地讲，循环层数和循环次数越大，程序运行得出结果所消耗的时间越长。

   任何在计算机上完成任务的程序运行，都需要在有限时间内解决问题，不然我们编写的程序就失去了意义。因而研究程序运行时间的有限性，远比研究程序执行时间的无限性更为重要。用算法程序执行中的指令重复执行次数来计算程序运行时间，是一种精确实用的计算方法。

   同一任务的算法不同，会产生程序执行时间的很大差异，与此有关的内容是属于最优算法研究的问题，但不是所谓“多项式时间复杂度”就能解决的问题。

Email accsys@126.com

2015-01-10