算法时间复杂度的批驳

       姜咏江

   在计算机程序运行的研究中，人们关心最多的是程序完成任务所消耗的时间。因而产生了一个“算法时间复杂度”的概念。什么是算法时间复杂度呢？

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

   上面这一段是从维基百科的定义翻译过来的。我们不仅要问这是概念的定义吗？既然是函数，为何又“不包括这个函数的低阶项和首项系数”？请问这样可以“定量描述了该算法的运行时间”吗？说到底，给出算法时间复杂度之初，并未找到计算算法程序运行时间的方法，因而才给出了这样模棱两可的所谓定义。实际上这种所谓的算法时间复杂度是不适于比较算法的优劣，也不能够定量描述算法的运行时间。

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

   我们知道，任何一个数n都可以表示成n = 的形式，其中a_i是十进制数码。依据“不包括这个函数的低阶项和首项系数”，那么O(n^k)= O(10^mk)。因为m是变量，故而mk也是变量，并且n趋于无穷大时，mk也趋于无穷大。令y=mk，于是有O(n^k)= O(10^y)。这就是说，所谓的多项式时间也是指数时间。可见所谓的多项式时间并不能够做为算法时间复杂度的简单度量方法。

   用大O表示方法不考虑幂多项式的较低项，毫无疑问失去了数学定量描述的意义。

   2015－6－15