算法时间复杂度与程序执行时间计算 多项式, 计算机程序

yuyang911220

转自：http://blog.sciencenet.cn/blog-340399-861142.html
简介：算法时间复杂度的研究，以所谓的多项式时间做为最低复杂度，由此认定只有多项式类型的算法程序执行最快，实在有些不靠谱。实际上计算机程序执行时间可以用其编译之后的机器语言程序来计算。因为每一机器指令（汇编指令）的指令周期都是确定的，故计算程序执行的时间，可先计算出每条机器指令重复执行次数，然后与指令周期相乘求和，最终获得准确时间。本文给出了的算法程序执行中指令重复执行次数的二元函数基本计算公式，依据该计算公式可以实际计算出程序运行的时间消耗，又提出了程序设计方法转换为一元函数之后，如何判定在同样的循环重复数之下，判定不同算法指令重复执行次数增加的快慢，进而判定各种算法程序执行时间的变化。
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，假设k=n，那么幂nn结构的n重循环用c语言描述如下。
for( i1=1; i0<=n; i1++){
for( i2=1; i1<=n; i2++){
  ......
for( in=1; in<=n; in++){
no1 += 1;
no2 += no1;
}}...}
for语句条件表达式的初值语句在每层只执行一次，而定界和步长语句都要执行n次。显然最内层每个语句重复循环次数是nn，向外各层依次为nn-1、nn-2、…、n2、n。那么总的语句重复执行次数为1+3n+3n2+3n3+…+3nn-2 +3nn-1+4nn。
对于一个程序，在顺序结构中，指令重复执行次数是1；在单层n次循环结构中，指令重复执行的次数是n；在k层n次循环当中写出的指令，其重复执行的次数是nk。于是各层指令重复执行的次数可用公式
f(n,k) = a0+a1n+a2n2+...+ak-1nk-1+aknk                                            （1）
来计算，其中ai是各循环层的写出指令数，i=0,1,2,...,k。
如果将公式（1）的k认为是常量，那么（1）式不就是一个多项式吗？我们能说这种形式的算法复杂度程序执行最快吗？
4.
计算类型实例
公式（1）中，若幂指数最高固定为常数k，则得到k次多项式；若幂底数固定为常数k，则得到指数多项式；若1层循环次数从1开始，逐层循环次数加1递增，则得到阶乘多项式。如此变化循环层数或循环次数，则可以得到各种重复执行计算的实际公式。为了说明这方面的演变，我们再举两个实例。
例2，将（1）式的幂底数（循环次数）设定为常数2，则能够得到指数型指令重复执行的多项式表达式a0+a12+a222+...+an-12n-1+an2n                          。
例3，设定幂底数是常数k，下面的循环结构可以实现nlogkn型的指令重复执行次数。
for( i=0; i<n; i++){
for( j=k; j<=n; j*=k){
no1 += 1;
no2 += no1;
}}
由j*=k知j的值循环变化序列为k,k2,k3,..., kt=n，于是内层循环次数t=logkn。
由于这个程序的外层循环次数是n，内层循环次数是logkn，因而程序指令重复执行次数总共是1+2n+n+4n logkn=1+3n+4n logkn。