伪多项式时间 Pseudo-polynomial time

2018-03-15 14:20:08

伪多项式时间：如果一个算法的传统时间复杂度是多项式时间的，而标准时间复杂度不是多项式时间的，则我们称这个算法是伪多项式时间的。

想要理解“伪多项式时间”，我们需要先给出“多项式时间”的一个清楚的定义。

对于“多项式时间”，我们的直观概念是时间复杂度 $O(n^{k} )$ ,其中 $k$ 是一常数。比如，选择排序的时间复杂度是 $O(n^{2} )$ ，是多项式时间；暴力解决TSP问题的时间复杂度是 $O(ncdot n!)$ ，不是多项式时间。我们称这种时间复杂度为“传统时间复杂度”。

我们通常认为传统时间复杂度中的变量 $n$ 表示数据的输入规模。比如，选择排序中， $n$ 指待排序数组中元素的个数；TSP问题中 $n$ 表示图中节点的数量。但是，这些所谓的输入规模，仅仅是直观的定义，并不足够严谨。为了标准化这些 $n$ ，在计算标准时间复杂度时，我们给出了输入规模的标准定义：

一个问题的输入规模是保存输入数据所需要的bit位数。

了解了输入规模的定义，我们来看“多项式时间”的标准定义：

对于一个问题，在输入规模为x的情况下，如果一个算法能够在O( $x^{k}$ )时间内解决此问题，则我们称此算法是多项式时间的，其中 $k$ 为一常数。

排序问题：用选择排序对元素个数为 $n$ 的数组进行排序时，传统时间复杂度为 $O(n^{2} )$ 。输入规模 $x=32n$ ，因此，得到的标准时间复杂度是 $O(x^{2} )$ ，仍然是多项式时间。因为这的n是只输入数据的数目。

素数测试：给定数字 n，通过从 2 到根号 n 的整数遍历，判断 n 是否为素数。看似时间复杂度是O(n)，但是这里的n是输入数字的大小，真实的输入规模为 x = logn，因此实际的时间复杂度是O(x ^ 2)，是指数级的时间复杂度。这就是个伪多项式时间复杂度。