多项式时间和 EXPTIME

小开

最佳答案

看看这个。

指数比多项式差。

O (n ^ 2)属于二次范畴，这是一种多项式(指数等于2的特殊情况) ，比指数更好。

指数比多项式差，看函数是如何增长的

n    = 10    |     100   |      1000


n^2  = 100   |   10000   |   1000000


k^n  = k^10  |   k^100   |    k^1000

K ^ 1000非常大除非 k 小于1.1。比如说，宇宙中的每一个粒子都必须每秒做1000亿亿次运算，持续数万亿亿年才能完成。

我没有计算出来，但它那么大。

小开

多项式时间。

多项式是看起来像 Constant * x^k的项的和指数意味着类似 Constant * k^x的东西

(在这两种情况下，k 是一个常数，x 是一个变量)。

指数算法的执行时间比多项式算法的执行时间增长快得多。

小开

O (n ^ 2)是多项式时间。多项式是 f (n) = n ^ 2。另一方面，O (2 ^ n)是 EXPTIME 的，其中暗示的指数函数是 f (n) = 2 ^ n。不同之处在于 n 的函数是将 n 放在指数的基数上，还是放在指数本身上。

任何指数增长函数都会比任何多项式函数(长期)增长得快得多，所以这种区别与算法的效率有关，特别是对于 n 的大值。

小开

指数 (如果最小一个指数依赖于一个参数，那么就有一个指数函数) :

例如 f (x) = 常数 ^ x

多项式 (如果没有指数依赖于某些函数参数，你有一个多项式函数) :

例如 f (x) = x ^ 常数

小开

O (n 序列)是多项式时间复杂度，o (2 ^ n)是 EXPTIME 复杂度如果 p = np 在最好的情况下，在最坏的情况下 p = np 不相等，因为当输入长度 n 增长得如此之长或者输入长度增加得如此之长时，它去最坏的情况和处理如此复杂的增长率增加并且依赖于输入的长度当输入很小时，它是多项式当输入长度很大时，p = np 不相等，这意味着增长率依赖于输入“ N”的长度。优化，坐标，小团体，和独立集也会在指数到多项式。

小开

多项式时间 O (n) ^ k 表示运算次数与输入大小的幂 k 成正比

EXPTIME O (k) ^ n 表示运算次数与输入大小的指数成正比

小开

下面是一些在分析算法时常用的 Big-O 函数。

O (1)-恒定时间
O (日志(n))-对数时间
O ((log (n)) < sup > c )-多对数时间
O (N)-线性时间
O (N < sup > 2 )-二次时间
O (N < sup > c )-多项式时间
O (C < sup > n )-EXPTIME
O (不！)-阶乘时间

(n = 输入大小，c = 某个常数)

这里的模型图表示一些函数的大 O 复杂度

干杯: -)

图表信用值 http://bigocheatsheet.com/

小开

以下是对新手最简单的解释:

多项式: 如果一个表达式包含或函数等于一个常数是一个变量的幂。

f(n) = 2 ^ n

同时

指数: 当一个表达式包含或函数等于一个变量是常数的幂时，例如。

f(n) = n ^ 2

小开

更精确的指数定义

多项式的定义是相当普遍和直接的，所以我不会进一步讨论它。

大 O的定义也是相当普遍的，你只需要仔细考虑维基百科定义中的 M和 x0，并通过一些例子来完成。

因此，在这个答案中，我想集中在指数的精确定义上，因为它需要更多的思考/不那么广为人知/不那么普遍，特别是当你开始考虑一些边缘情况时。然后我将它与下面的多项式进行对比

对 EXPTIME 最常见的定义是:

2^{polymonial(n)}

其中 polynomial是一个多项式:

不是常数，例如 1，否则时间也是常数
最高阶项有一个正系数，否则它在无穷远处趋于零，例如 2^{-n^2 + 2n + 1}

所以这样的多项式是好的:

2^{n^2 + 2n + 1}

注意，基数2可以是任意大于1的数字，定义仍然有效，因为我们可以通过乘以指数来转换基数，例如:

8^{polymonial(n)} = (2^3)^{polymonial(n)} = 2^{3 * polymonial(n)}

3 * polymonial(n)也是一个多项式。

还要注意，常数相加并不重要，例如 2^{n + 1} = 2 * 2^{n}，因此对于大 O 符号，+ 1也不重要。

因此，对于规范的“最小指数”，两个可能的大 O 等价选择对于任何小的正值 e都是:

(1 + e)^{n}
2^{en}

对于非常小的 e。

在这两种情况下，指数多项式的最高阶项是 n^1，一阶，因此是最小可能的非常数多项式。

这两种选择是等价的，因为如前所述，我们可以将基数变化转换为指数乘数。

超多项式和次指数

但请注意，上面的定义排除了一些在实践中出现的仍然非常大的事情，我们可能会称之为“指数”，例如:

2^{n^{1/2}}.这有点像多项式，但它不是多项式，因为多项式的幂必须是整数，这里我们有 1/2
2^{log_2(n)^2}

这些函数仍然非常大，因为它们比任何多项式增长得都快。

但严格来说，它们是大 O 小于我们严格定义的指数！

这促成了下列定义:

超多项式: 比任何多项式增长得都快
次指数增长: 增长速度低于任何指数，即 (1 + e)^{n}

本节给出的所有例子都属于这两个类别。

请记住，如果你把一些非常小的东西放在指数上，它当然可能回到多项式，例如:

2^{log_2(n)} = n

对于任何小于 log_2的情况也是如此，例如:

2^{log_2(log_2(n))} = log_2(n)

是次多项式。

重要的超多项式和次指数例子

普通数域筛选法2020年最快的整数分解算法参见: 最快的整数分解算法是什么？该算法具有复杂的形式:
```
e^{(k + o(1))(ln(n)^(1/3) * ln(ln(n)))^(2/3)}
```
其中 n是因子数，小 -o 符号 o(1)表示一个在无穷远处趋向于0的项。

这种复杂性甚至有一个命名的泛化，因为它可能发生在其他分析中: L 符号。

注意，上面的表达式本身在 n中显然是多项式的，因为它比 e^{ln(n)^(1/3) * ln(n))^(2/3)} = e^{ln(n)} = n小。

然而，在因数分解的上下文中，真正重要的是注意 n，而不是“ n的位数”，因为加密方可以轻松地生成两倍大的加密密钥。数字的数量随着 log_2的增长而增长。所以在这种复杂性中，我们真正关心的是:
```
e^{(k + o(1))(n^(1/3) * ln(n)^(2/3)}
```
当然是超多项式和次指数的。

这个奇妙的答案是: 什么会导致算法具有 O (log log n)复杂度？给出了一个关于 O(log log n)来自哪里的直观解释: 而 log n来自于一个算法，它在每个步骤中删除了一半的选项，而 log log n来自于一个算法，它在每个步骤中将选项减少到总数的平方根！
Https://quantumalgorithmzoo.org/ 包含了一系列可能会引起量子计算机兴趣的算法，并且在大多数情况下，相对于经典计算机的量子加速并不是严格的指数型的，而是超多项式的。然而，正如这个答案希望强调的那样，这仍然是极其重要和革命性的。理解这个存储库是最初激发这个答案的原因: -)

同样值得注意的是，我们目前并不期望量子计算机能够解决 NP 完全问题，而这些问题通常也需要 EXPTIME 来解决。但也没有其他证据。参见: https://cs.stackexchange.com/questions/130470/can-quantum-computing-help-solve-np-complete-problems

Https://math.stackexchange.com/questions/3975382/what-problems-are-known-to-be-require-superpolynomial-time-or-greater-to-solve 询问任何已被证明为超多项式的有趣算法(假设有最优性的证明，否则一般数字筛将是一个明显的选择，但我们不知道2020-知道它是否是最优的)

证明指数在无穷远处总是大于多项式

Https://math.stackexchange.com/questions/3975382/what-problems-are-known-to-be-require-superpolynomial-time-or-greater-to-solve

关于次指数不同可能定义的讨论

小开

多项式的例子: n ^ 2，n ^ 3，n ^ 100,5n ^ 7，等等..。

指数例子: 2 ^ n，3 ^ n，100 ^ n，5 ^ (7n) ，等等..。