关于多项式时间的辨析

姜咏江

   在P/NP的问题中，不论是通俗的定义还是在形式语言的定义中，都将所谓的多项式时间做为重要的基础概念。什么是多项式时间？本文从计算机程序执行时间计算的角度出发，给出了程序执行时间计算的基本公式，并在该公式的基础上进行所谓多项式时间辨析。

1.              什么是多项式？

   在数学中人们将形式的表达式一般称为多项式，其中x是变量，n是某一个确定的自然数，a_i是第i项的系数。从函数的观点看有函数f(x) = 。其实，多项式的项是一种乘积的形式，而将多个乘积的表达式用加号连接起来，就得到了一个多项式。为此多项式还有函数g(x) = ，它的右侧表达式又可以叫指数多项式；如果将幂底数和幂指数都认定是变量，那么就有二元函数j(x, y) = ，右面的表达式又叫幂多项式。

2.              如何理解计算机程序执行时间计算？

   众所周知，计算机是靠主频的时钟周期来划分时间单位的。一个时钟周期决定着计算机的一个基本状态。算法程序执行时间完全可以用其消耗的主频时钟周期计算出来。图灵机并没有这种实际严格的时间计算，但我们可以认为图灵机的每一次状态变换都需要一个统一的固定时间，这样就可以在假定时间单位下讨论时间消耗多少的问题了。

   不论图灵机还是只有一个处理器的计算机，它们都遵循着线性顺序处理方式的特点来进行动作，因而计算算法程序执行的时间消耗，必然要遵从线性顺序处理方式的计算方法。这就是说计算机从程序启动的时刻起，所有的计时应为基本动作时间的总和，最终都可以用一个自然数来表示某种单位时间。

   在这个数学计量过程中，可以依据某种条件来划分出计量的分段，这种分段我们称之为计量段。任何一个计量段都是有限的，而且最多只能进行有限次重复计量，不然就无法得到任何有效的计量结果。

   如果某计量段的一次计量用自然数n表示，而有限重复的次数用c来表示，那么这段线性计量值就可以用c×n表示。当重复次数c恰好等于n的时候，就可以出现n×n=n²的情况。如果重复次数恰好为c=a×n^k-1的形式（a是一个不等于n的数，k是一个自然数），那么计量的表达式中就会出现c×n=a×n^k-1×n=an^k这种表达式。如果我们探讨的是多个不同计量段的情况，就会出现              

                        （ij）

的计算公式，其中n和k是幂底数和幂指数中的最大数，a_ij称为系数。我们称公式（ij）为幂多项式。

   幂多项式（ij）只有在极特殊的情况下才会成为幂底数n是一个变量x，最高幂指数k为常数的所谓“多项式”，此时公式（ij）就成为了 ；而当幂底数n为常数，幂指数k为变量x的时候，才能使（ij）成为所谓的“指数多项式”，那么公式（ij）就成为了 的形式。

   算法是程序设计的方法。一种算法客观上就规定了一个计算机程序执行的顺序，从前面谈到的时间计算来看，就成了一种划分时间段及重复计量的一种方法。

3.              程序执行时间都可以表达成幂多项式

   在图灵机或现代计算机上，任何有解算法程序执行时间，不论如何，总能够用一个自然数表达出来，不然就与算法程序有解相悖。尽管有些问题的算法完成执行过程，恐怕要用人类都无法等待的时间才能完成，但聪明的人类可以不用等到那个结束的时候，而是采用数学方法计算出计算机能够解决这个问题所用的时间。因而研究计算算法执行时间具有十分重要的实际意义。

   我们从计算机线性动作的基本方式出发，一般性地讨论了算法程序执行时间计算的基本形式（ij），但这个表达式似乎对我们过于抽象。能不能从算法的角度说明（ij）公式中各个标识符所表达的实际意义？过去，许多人认为不可能确切地计算出程序执行的时间，其实这是完全可以办到的事情。

   从计算机程序设计的基本结构来看，任何程序不外乎有顺序、分支、循环和子程序调用这四种基本结构。分支是有选择的顺序，而子程序可以镶嵌到调用点，使其变为顺序。这样一来，所有的程序都可以转化成顺序、分支和循环这三种基本结构。

   虽然在算法设计当中有这三种基本结构，但在一个处理器上，算法程序实际执行中，一律都必须转化成一维线性有序执行的方式，即以机器基本动作的先后方式完成程序执行。这种执行方式可以通过（ij）幂多项式来计算基本动作的发生次数，其中n是多层循环结构的第n层循环次数，k是循环嵌套层数，a_nk是循环体基本动作单位数。

   如果我们更一般化地考虑基本动作单位是什么？那么可以认为在图灵机上就是一次状态转移，在现代计算机上就是一条机器微指令，在一般编程语言中，就认为是一个语句。在一般性编程语言中，虽然每个语句执行的时间不同，但这并不失问题探讨的一般性，因而我们仍然可以假定它们执行的时间相同。

4.              相关讨论

   算法程序执行时间的计算无疑是关系到算法时间复杂度的决定因素。有关算法程序执行时间是由指令（基本动作）重复执行次数的多少来决定的，而指令重复执行次数又是由程序结构的循环层数k、层内循环次数n和各层内部指令数a三个量所确定。有关对算法时间复杂度的辨析，我们将放到另外的篇幅中讨论。

2015-06-03