什么是假多项时间？ 它与多项式时间有什么不同？
什么是假多项时间 ？ 它与多项式时间有什么不同？ 在假多项式时间运行的一些algorithm具有如O（nW）（对于0/1背包问题 ）或O（√n）（用于试划分 ）的运行时间; 为什么不算多项式时间呢？
为了理解多项式时间和伪多项式时间之间的差异，我们需要通过forms化“多项式时间”的含义来开始。
多项式时间的一般直觉是“对于某个k的时间O（n k ）”。 例如， selectsorting在时间O（n 2 ）中运行，这是多项式时间，而蛮力求解TSP则需要时间O（n·n！），这不是多项式时间。
这些运行时间都是指跟踪input大小的variablesn。 例如，在selectsorting中，n表示数组中元素的数量，而在TSP中，n表示图中节点的数量。 为了规范在这种情况下“n”实际意义的定义，时间复杂度的正式定义将问题的“规模”定义如下：
问题input的大小是写出该input所需的位数。
例如，如果sortingalgorithm的input是32位整数数组，那么input的大小将是32n，其中n是数组中的条目数。 在具有n个节点和m个边的图中，input可以被指定为所有节点的列表，后面是所有边的列表，这将需要Ω（n + m）个比特。
给定这个定义，多项式时间的forms定义如下：
如果某个常数k的运行时间为O（ xk ），则algorithm运行在多项式时间内，其中x表示给algorithm的input位数。
在处理graphics，列表，树等的algorithm时，这个定义或多或less地符合传统的定义。 例如，假设您有一个sortingalgorithm来对32位整数数组进行sorting。 如果使用selectsorting来做到这一点，则运行时作为数组中input元素数量的函数将是O（n 2 ）。 但是，input数组中元素的数量n是如何对应于input的位数？ 如前所述，input的位数是x = 32n。 因此，如果我们用x来表示algorithm的运行时间而不是n，那么运行时间是O（x 2 ），所以algorithm运行在多项式时间内。
同样，假设你在一个图上进行深度优先search ，这需要时间O（m + n），其中m是图中边的数量，n是节点数。 这与给定input的位数有什么关系？ 那么，如果我们假设input被指定为邻接表（所有节点和边的列表），则如前所述，input位的数量将是x =Ω（m + n）。 因此，运行时将是O（x），所以algorithm运行在多项式时间。
然而，当我们开始谈论运算数字的algorithm时，事情就会崩溃。 让我们来考虑一下testing一个数字是否为素数的问题。 给定一个数n，可以使用以下algorithmtestingn是否为素数：
function isPrime(n): for i from 2 to n - 1: if (n mod i) = 0, return false return true 那么这个代码的时间复杂度是多less？ 那么，内部循环运行O（n）次，每次做一些工作来计算n mod i（作为一个非常保守的上限，这当然可以在时间O（n 3 ））完成。 因此，这个总体algorithm运行时间O（n 4 ），可能要快得多。
2004年，三位计算机科学家发表了一篇名为PRIMES的文章，其中给出了一个多项式时间algorithm来testing一个数是否为素数。 这被认为是一个里程碑式的结果 那么有什么大不了的？ 我们是不是已经有了一个多项式时间algorithm，就是上面那个？
不幸的是，我们没有。 请记住，时间复杂度的正式定义会根据input的位数来说明algorithm的复杂性。 我们的algorithm在时间O（n 4 ）中运行，但是这是什么作为input比特数的函数？ 那么写出数字n需要O（log n）位。 因此，如果我们令x是写出inputn所需的位数，则algorithm的运行时间实际上是O（2 4x ），这不是 x中的多项式。
这是多项式时间和伪多项式时间区分的核心。 一方面，我们的algorithm是O（n 4 ），看起来像一个多项式，但另一方面，在多项式时间的forms定义下，它不是多项式时间。
为了直观地说明algorithm为什么不是多项式时间algorithm，请考虑以下内容。 假设我想要algorithm必须做很多工作。 如果我写出这样的input：
10001010101011
那么T就需要花费一些最坏的时间来完成。 如果我现在添加一个数字的末尾，像这样：
100010101010111
运行时现在（在最坏的情况下）是2T。 我可以将algorithm的工作量增加一倍！
如果运行时间是input数值中的某个多项式，而不是表示它的位数，则algorithm运行在假多项式时间 。 我们的主要testingalgorithm是一个伪多项式时间algorithm，因为它运行时间为O（n 4 ），但它不是一个多项式时间algorithm，因为作为写入input所需的位数x的函数，运行时间是O （2 4x ）。 “PRIMES在P”文件中的原因非常显着，其运行时间（大致）为O（log 12 n），作为位数的函数是O（x 12 ）。
那为什么这个问题呢？ 那么，我们有许多用于分解整数的假多项式时间algorithm。 然而，从技术上讲，这些algorithm是指数时间algorithm。 这对于密码学非常有用：如果你想使用RSAencryption，你需要能够相信我们不能轻易地分解数字。 通过将数字中的位数增加到一个巨大的数值（比如1024位），可以使假多项分解algorithm必须采用的时间量非常大，以至于完全并且完全不可能将数字。 另一方面，如果我们可以find一个多项式时间分解algorithm，情况并不一定如此。 增加比特数可能会使工作增长很多，但增长只会是多项式增长，而不是指数增长。
也就是说，在很多情况下，伪多项式时间algorithm是完美的，因为数字的大小不会太大。 例如， 计数sorting具有运行时O（n + U），其中U是数组中的最大数字。 这是伪多项式时间（因为U的数字值需要O（log U）位写出，所以运行时间在input大小上是指数的）。 如果我们人为地约束U使得U不是太大（例如，假设U是2），那么运行时间是O（n），实际上它是多项式时间。 这就是基数sorting的工作原理：通过每次处理一位数字，每一轮的运行时间是O（n），所以整个运行时间是O（n日志U）。 这实际上是多项式时间，因为写出n个数字来sorting使用Ω（n）位，并且log U的值与写入arrays中最大值所需的位数成正比。
希望这可以帮助！
伪多项式时间复杂度是指input的值/幅度中的多项式，但是input的大小是指数的。
大小是指写入input所需的位数。
从背包的伪码中，我们可以发现时间复杂度为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, jw[i]] + v[i]) else m[i, j] := m[i-1, j] end if end for end for
这里，W不是input长度的多项式，而是伪多项式。
设s是表示W所需的比特数
ie 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），它不是多项式。
