多项式时间

多项式时间

问题一：什么叫多项式时间算法 10分定义：若存在一个常数C，使得对于所有n>=0，都有|f(n)| 问题二：多项式时间的定义 多项式时间（Polynomial time）在计算复杂度理论中，指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可于此机器以多项式时间求解的问题。问题三：多项式时间 什么是多项式时间 就是算法消耗的时间，与规模n呈多项式（O(n^k)）的关系问题四：什么是概率多项式时间 概率多项式时间（Polynomial time）在计算复杂度理论中，指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可于此机器以多项式时间求解的问题。
数学家有时把“比多项式时间长的算法”视为快速计算，相对应的是超多项式时间，表示任何多项式时间的输入数目只要够大，超多项式时间所需的解题时间终究会大大超过任何多项式时间的问题。指数时间（Exponential time）就是一例。
超多项式时间：O(c^f(n))，其中畅为大于1的常数，f(n)大于常数，小于线性。
可以在决定型依序机器上（例如图灵机）以多项式时间解决的决定性问题，其属于的复杂度类被称为P。可以在多项式时间验证答案的非决定性问题称为NP。而NP也是可以在非确定型图灵机以多项式时间解决的问题（NP两字为Non-deterministic Polynomial的缩写）。问题五：多项式时间的介绍 多项式时间在决定型机器上是最小的复杂度类别，且在机器模型改变时依旧强韧，且也是可在副程式组合过程中保持封闭的类别。问题六：什么是多项式时间内可解的问题，举个例子说明 多项式时间，就是所需时间是规模的多项式函数，典型的例子是
1次函数f(n)=kn+b问题七：什么是伪多项式时间算法 想要理解“伪多项式时间”，我们需要先给出“多项式时间”的一个清楚的定义。
对于“多项式时间”，我们的直观概念是时间复杂度,其中是一常数。比如，选择排序的时间复杂度是，是多项式时间；暴力解决TSP问题的时间复杂度是，不是多项式时间。我们称这种时间复杂度为“传统时间复杂度”。
我们通常认为传统时间复杂度中的变量表示数据的输入规模。比如，选择排序中，指待排序数组中元素的个数；TSP问题中表示图中节点的数量。但是，这些所谓的输入规模，仅仅是直观的定义，并不足够严谨。为了标准化这些，在计算标准时间复杂度时，我们给出了输入规模的标准定义：
一个问题的输入规模是保存输入数据所需要的bit位数。
比如，如果排序算法的输入是一个32-bit整数 数组，那么输入规模就是，是指数组中元素的个数。对于一个带有个节点、条边的图，需要的bit位数就是。
了解了输入规模的定义，我们来看“多项式时间”的标准定义：
对于一个问题，在输入规模为x的情况下，如果一个算法能够在O()时间内解决此问题，则我们称此算法是多项式时间的，其中为一常数。
当我们处理一些图论、链表、数组、树等问题时，这个标准定义下的多项式时间和我们传统的多项式时间相差无几。比如，用选择排序对元素个数为的数组进行排序时，传统时间复杂度为。输入规模，因此，得到的标准时间复杂度是，仍然是多项式时间。
类似的，假设在带有个节点、条边的图中做DFS(深度优先搜索)，传统时间复杂度为。数据规模，因此，标准时间复杂度是，仍是多项式时间的。
然而，当我们处理一些与数论有关的问题时，事情就不太乐观了。现在我们来讨论判断一个整数是否为素数的算法，下面是一个简单的算法：
function isPrime(n):
for i from 2 to n - 1:
if (n mod i) = 0, return false
return true
显然，这个算法在传统时间复杂度计算方法中是多项式时间的。我们不妨认为它的传统时间复杂度是。然后我们再来分析这个问题的输入规模，可能有的同学会说，对于32-bit整数，这个输入规模不就是32吗？这话虽然没错，但是因为在这个问题中，输入规模完全依赖于的大小，所以的范围不再限制在32-bit整数的范围内，而是要探讨当更大时对数据规模的影响。我们知道，保存一个整数所需要的bit位数，因此，在标准的时间复杂度中，此算法的复杂度变为了!这已经不再是多项式时间，而是一个指数时间。
我们可以从下面这个例子中直观感受一下这种指数时间的增长速度：
对于一个二进制串：
10001010101011
我们记指数时间复杂度算法运行时间为T。
然后，我们在二进制串后面仅仅增加一位：
100010101010111
这时，算法运行时间会变为2T(至少)！因此，我们仅仅增加几个bit 就会使得算法运行时间成倍成倍的增长。

感谢回答