121

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

4

2 回答 2

297

要理解多项式时间和伪多项式时间之间的区别，我们需要从形式化“多项式时间”的含义开始。

多项式时间的常见直觉是“某个 k 的时间 O(n k )”。例如，选择排序在 O(n 2 ) 时间内运行，这是多项式时间，而暴力求解TSP需要时间 O(n · n!)，而不是多项式时间。

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

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

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

给定这个定义，多项式时间的正式定义如下：

如果某个常数 k 的运行时间为 O(x k )，则算法在多项式时间内运行，其中 x 表示算法输入的位数。

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

同样，假设您在图上进行深度优先搜索，这需要时间 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 3 ) 时间内完成）。因此，这个整体算法运行时间为 O(n 4 ) 并且可能快得多。

2004 年，三位计算机科学家发表了一篇名为PRIMES 在 P 中的论文，给出了一个多项式时间算法来测试一个数是否为素数。这被认为是一个里程碑式的结果。那么有什么大不了的呢？我们不是已经有了一个多项式时间算法，即上面的那个吗？

不幸的是，我们没有。请记住，时间复杂度的正式定义将算法的复杂度描述为输入位数的函数。我们的算法运行时间为 O(n 4 )，但是作为输入位数的函数，它是什么？好吧，写出数字 n 需要 O(log n) 位。因此，如果我们让 x 为写出输入 n 所需的位数，则该算法的运行时间实际上是 O(2 4x )，它不是x 中的多项式。

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

要了解为什么该算法不是多项式时间算法，请考虑以下问题。假设我希望算法必须做很多工作。如果我写出这样的输入：

10001010101011

那么这将需要一些最坏情况下的时间，比如说T，完成。如果我现在在数字末尾添加一个位，如下所示：

100010101010111

运行时间现在（在最坏的情况下）将是 2T。只需再增加一位，我就可以使算法的工作量翻倍！

如果运行时间是输入的数值中的某个多项式，而不是表示它所需的位数，则算法在伪多项式时间内运行。我们的主要测试算法是伪多项式时间算法，因为它在 O(n 4 ) 时间内运行，但它不是多项式时间算法，因为作为写出输入所需的位数 x 的函数，运行时间是 O （2 4 倍）。“PRIMES is in P”论文之所以如此重要，是因为它的运行时间（大致）为 O(log 12 n)，作为比特数的函数，它是 O(x 12 )。

那么这有什么关系呢？好吧，我们有许多用于因式分解整数的伪多项式时间算法。但是，从技术上讲，这些算法是指数时间算法。这对密码学非常有用：如果你想使用 RSA 加密，你需要能够相信我们不能轻易地分解数字。通过将数字中的位数增加到一个巨大的值（例如，1024 位），您可以使伪多项式时间因式分解算法必须花费的时间变得如此之大，以至于完全无法分解数字。另一方面，如果我们可以找到多项式时间分解算法，则不一定是这种情况。添加更多位可能会导致工作大量增长，但增长只会是多项式增长，而不是指数增长。

也就是说，在许多情况下，伪多项式时间算法非常好，因为数字的大小不会太大。例如，计数排序的运行时间为 O(n + U)，其中 U 是数组中的最大数。这是伪多项式时间（因为 U 的数值需要 O(log U) 位才能写出，因此运行时间是输入大小的指数）。如果我们人为地限制 U 以使 U 不太大（例如，如果我们让 U 为 2），那么运行时间是 O(n)，实际上是多项式时间。这就是基数排序的工作原理：通过一次一位地处理数字，每一轮的运行时间为 O(n)，因此总运行时间为 O(n log U)。这实际上是多项式时间，因为写出 n 个要排序的数字使用 Ω(n) 位，并且 log U 的值与写出数组中最大值所需的位数成正比。

希望这可以帮助！

于 2013-10-29T00:38:47.927 回答
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)

现在，running time of knapsack= O(nW) = O(n * 2^s) 这不是多项式。

于 2015-02-15T19:45:53.867 回答