什么是伪多项式时间？它与多项式时间有何不同？

Question

什么是伪多项式时间？它与多项式时间有何不同？

algorithmbig-otime-complexity

127

伪多项式时间是什么？它与多项式时间有何不同？一些运行在伪多项式时间的算法，其运行时间类似于O(nW)（对于0/1背包问题）或O(√n)（对于试除法）；为什么这不算作多项式时间？

- templatetypedef

相关帖子 - 阶乘递归算法的复杂度 - RBT

2个回答

3

伪多项式时间复杂度指的是输入值或大小为多项式级别，但输入大小却呈指数级别。

所谓大小是指写入输入所需的位数。

从背包问题的伪代码中，我们可以得出时间复杂度为O(nW)。

// Input:
// Values (stored in array v) 
// Weights (stored in array w)
// Number of distinct items (n) //
Knapsack capacity (W) 
for w from 0 to W 
    do   m[0, w] := 0 
end for  
for i from 1 to n do  
        for j from 0 to W do
               if j >= w[i] then 
                      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i]) 
              else 
                      m[i, j] := m[i-1, j]
              end if
       end for 
end for

在这里，W并不是多项式级别的，但这正是使它成为伪多项式时间复杂度的原因。

设s表示表示W所需的比特数。

i.e. size of input= s =log(W) (log= log base 2)
-> 2^(s)=2^(log(W))
-> 2^(s)=W  (because  2^(log(x)) = x)

现在，knapsack问题的运行时间= O(nW) = O(n * 2^s)，这并不是多项式时间。

- Adi agarwal

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

为了理解多项式时间和伪多项式时间的区别，我们需要首先明确“多项式时间”的含义。

多项式时间的普遍直觉是“时间复杂度为O(n^k)（其中k为某个常数）”。例如，选择排序的时间复杂度为O(n^2)，这是多项式时间，而暴力求解TSP的时间复杂度为O(n·n!)，不是多项式时间。

这些运行时间都涉及一个变量n，用于跟踪输入的大小。例如，在选择排序中，n指数组中元素的数量，而在TSP中，n指图中节点的数量。为了标准化“n”在此上下文中实际意义的定义，时间复杂度的正式定义将问题的“大小”定义如下：

问题的输入大小是编写该输入所需的位数。

例如，如果排序算法的输入是一个包含32位整数的数组，则输入大小为32n，其中n是数组中条目的数量。在具有n个节点和m条边的图中，输入可以被指定为所有节点的列表，后跟所有边的列表，这将需要Ω(n + m)位。

鉴于这个定义，多项式时间的正式定义如下:

如果一个算法的运行时间为O(x^k)，其中x表示输入给算法的比特数，则该算法在多项式时间内运行。

当处理图形、列表、树等算法时，这个定义或多或少与传统的定义相符。例如，假设您有一个排序算法，用于对32位整数数组进行排序。如果使用选择排序之类的算法，其运行时间作为输入元素数量的函数，将是O(n²)。但是，输入数组中元素数量n如何与输入位数的数量相对应？如前所述，输入位数将为x = 32n。因此，如果我们用x而不是n表示算法的运行时间，我们得到算法的运行时间为O(x²)，因此该算法在多项式时间内运行。

同样地，假设您在图上执行深度优先搜索（depth-first search），这需要时间O（m + n），其中m是图中边的数量，n是节点的数量。这与给定输入位数有何关系？如果我们假设输入被指定为邻接表（所有节点和边的列表），则如前所述，输入位数将为x = Ω（m + n）。因此，运行时间将为O（x），因此算法在多项式时间内运行。

然而，当我们开始讨论操作数字的算法时，情况就会变得复杂起来。让我们考虑测试一个数字是否为质数的问题。给定一个数字n，您可以使用以下算法测试n是否为质数：

function isPrime(n):
    for i from 2 to n - 1:
        if (n mod i) = 0, return false
    return true

那么这段代码的时间复杂度是什么？嗯，内部循环运行了O(n)次，并且每次都要做一些计算n mod i的工作（作为一个非常保守的上界，这可以在O(n³)的时间内完成）。因此，这个整体算法的时间复杂度为O(n⁴)，可能会快得多。

2004年，三位计算机科学家发表了一篇名为PRIMES is in P的论文，提出了一种多项式时间算法来测试一个数是否为质数。这被认为是一个里程碑式的成果。那么这有什么大不了的？难道我们不已经有了一个多项式时间算法吗，就是上面那个算法吗？

很遗憾，我们没有。请记住，时间复杂度的正式定义是关于算法复杂性的一个函数，作为输入位数的函数。我们的算法运行时间为O(n⁴)，但作为输入位数的函数是多少呢？好吧，写出数字n需要O(log n)位。因此，如果我们将x定义为编写输入n所需的位数，那么该算法的运行时间实际上是O(2^4x)，这不是x的多项式。

这是多项式时间和伪多项式时间之间区别的核心。一方面，我们的算法是O(n⁴)，看起来像一个多项式，但另一方面，在多项式时间的正式定义下，它不是多项式时间。

为了对算法为什么不是多项式时间算法有直觉感受，考虑以下情况。假设我希望算法需要做很多工作。如果我写出这样的输入：

10001010101011

然后它将需要一些最坏情况下的时间，比如 T，来完成。如果我现在在数字结尾添加一个单独的位，像这样：

100010101010111

在最坏情况下，运行时间现在将是 2T。只需添加一个位，就可以使算法的工作量增加一倍！如果运行时间是输入数值的某个多项式，而不是表示它所需的位数的多项式，则算法以伪多项式时间运行。我们的质数测试算法是一个伪多项式时间算法，因为它的运行时间是 O(n⁴)，但它不是一个多项式时间算法，因为作为输入所需的位数 x 的函数，运行时间是 O(2^4x)。PRIMES 在 P 中的论文之所以如此重要，是因为其运行时间（大约）是 O(log¹² n)，作为位数的函数是 O(x¹²)。

因此，这有什么影响呢？我们有许多伪多项式时间算法用于因数分解整数。然而，这些算法在技术上来说是指数级别的算法。这对于加密非常有用：如果您想使用RSA加密，您需要相信我们不能轻易地分解数字。通过将数字中的位数增加到巨大值（比如1024位），您可以使伪多项式时间分解算法所需的时间变得如此之长，以至于分解数字完全不可行。另一方面，如果我们能够找到一个多项式时间因数分解算法，情况并非总是如此。增加更多位可能会导致工作量大大增加，但增长只会是多项式增长，而不是指数增长。

话虽如此，很多情况下伪多项式时间算法是完全可以接受的，因为数字的大小不会太大。例如，计数排序的运行时间为 O(n + U)，其中 U 是数组中最大的数字。这是伪多项式时间（因为数值 U 需要 O(log U) 位才能写出，所以运行时间在输入大小上是指数级的）。如果我们人为地限制 U 不要太大（比如说，我们让 U 等于 2），那么运行时间就是 O(n)，实际上是多项式时间。这就是基数排序的工作原理：逐位处理数字，每轮的运行时间是 O(n)，因此总运行时间是 O(n log U)。这实际上是多项式时间，因为将 n 个数字排序写出需要 Ω(n) 位，而 log U 的值与写出数组中最大值所需的位数成正比。