算法多项式时间复杂度不靠谱的证明

姜咏江

   可笑的是算法时间复杂度的所谓多项式时间O(n^k)，说k是常量，n是变量，n^k叫多项式。在算法时间复杂度又说cⁿ是指数型，c是常数，n是变量。O(n^k)与O(cⁿ)是两种不同的时间复杂度。

   算法理论中的多项式为P=，其中a_i是系数，k是确定的正整数，n是整型变量。我们知道，任何一个整数n都可以表示成n = 的形式，其中b_j是十进制数码。由于两个多项式的算数运算结果仍然是多项式，于是有

P=。这样变化之后，P的各项都变成了指数形式，最高项为a_kn^k= a_kb_m^k10^mk。

例如，n=10⁰+3×10^m，P=5n+n²，则有

P = 5(1+3×10^m)+ (1+3×10^m)²

= 5+15×10^m+1+6×10^m+9×10^2m

= 6+21×10^m+9×10^2m。

最高阶项n²变成了9×10^2m。

   依据算法时间复杂度所说：“不包括这个函数的低阶项和首项系数”，那么经过变换就有O(n^k) = O(10^mk)，其中m是依据变量n而变化的变量，故而mk也是变量，并且当n趋于无穷大时，mk也趋于无穷大。不妨令y=mk，于是有

O(n^k)= O(10^y)。这就是说，用大O表示的所谓多项式时间也是指数时间！

   其实算法程序执行时间可以用这样的幂多项式计算，一般所说的那种指数为常量的表达只是一种形式，它可以转化成指数为变量的一种表达方式，这两种表达方式无疑是等价的。然而若“掐头去尾”用最高指数项去替代，这种等价性就丧失了。

   通过以上的等式变化足可以说明，所谓用大O表示的算法时间复杂度是不靠谱的方法，在概念上存在问题。

   用大O表示的算法时间复杂度是不靠谱的关键，就是计量时所说的“不包括这个函数的低阶项和首项系数”，这是产生误差的关键所在。因而研究算法时间复杂度必需考虑算法程序执行时间的全部。

   有关这方面的问题，我已经在博文http://blog.sciencenet.cn/blog-340399-887347.html和

http://blog.sciencenet.cn/blog-340399-861142.html中有初步阐述。不久会全面整理供有心研究P/NP者共同讨论。

2015-6-16