要了解多项式时间和伪多项式时间之间的差异，我们需要从形式上定义“多项式时间”的含义开始。

多项式时间的直觉是“ 某个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 is
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
4x）。“ PRIMES 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的值与写出数组中最大值所需的位数成正比。

希望这可以帮助！