多项式时间和指数时间

Question

我有一个关于多项式时间算法,非多项式时间算法和指数时间算法之间差异的问题,例如,如果一个算法需要O(n ^ 2)时间,那么它将属于哪个类别？

Answer 1

下面是分析算法时常见的Big-O函数.

• O(1) - 恒定时间
• O(log(n)) - 对数时间
• O((log(n))^c) - 多对数时间
• O(n) - 线性时间
• O(n ²) - 二次时间
• O(n ^c) - 多项式时间
• O(c ⁿ) - 指数时间

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

这是表示某些函数的Big-O复杂性的模型图

欢呼:-)

图表学分http://bigocheatsheet.com/

Answer 2

看一下这个

http://en.wikipedia.org/wiki/Big_oh#Orders_of_common_functions

指数比多项式差.

O(n ^ 2)属于二次类,这是一种多项式(指数的特殊情况等于2)并且优于指数.

指数是多少比多项式更糟糕.看看这些功能如何发展

n    = 10    |     100   |      1000

n^2  = 100   |   10000   |   1000000 

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

除非k小于1.1,否则k ^ 1000非常大.就像宇宙中的每个粒子一样,每秒数亿亿亿次操作需要花费数万亿甚至数十亿年才能完成.

我没有计算出来,但它很大.

Answer 3

O(n ^ 2)是多项式时间.多项式是f(n)= n ^ 2.另一方面,O(2 ^ n)是指数时间,其中隐含的指数函数是f(n)= 2 ^ n.不同之处在于n的函数是否将n置于求幂的基础中,还是置于指数本身中.

任何指数增长函数将比任何多项式函数显着更快(长期)增长,因此区别与算法的效率相关,特别是对于大的n值.

Answer 4

多项式时间.

多项式是项的线性组合,看起来像Constant * x^k 相反,指数意味着类似的东西Constant * k^x,其中在两种情况下k是常数而x是变量.

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

Answer 5

指数(如果MINIMAL ONE EXPONENT依赖于参数,则您具有指数函数):

• 例如f(x)=常数^ x

多项式(如果NO EXPONENT依赖于某些函数参数,则您具有多项式函数):

• 例如f(x)= x ^常数

Answer 6

指数的更精确定义

多项式的定义非常通用且简单，因此我不会进一步讨论它。

Big O的定义也很普遍，你只需要仔细思考维基百科定义中的theM和 the并通过一些例子来理解即可。x0

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

• https://cstheory.stackexchange.com/questions/22588/is-it-right-to-call-2-sqrtn-exponential
• https://math.stackexchange.com/questions/55468/how-to-prove-that-exponential-grows-faster-than-polynomial

指数时间最常见的定义是：

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}，因此+ 1对于大 O 表示法来说并不重要。

因此，对于规范的“最小指数”，两个可能的大 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}

本节上面给出的所有示例都属于这两类。TODO 证明。

请记住，如果您在指数上放置非常小的东西，它当然可能会回到多项式，例如：

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。

  然而，在分解的背景下，真正重要的是 note n，而是“ 的位数n”​​，因为密码学各方可以轻松生成两倍大的加密密钥。并且位数随着 增长log_2。因此，在这种复杂性中，我们真正关心的是：

  e^{(k + o(1))(n^(1/3) * ln(n)^(2/3)}
  

  这当然是超多项式和次指数的。

  奇妙的答案是：什么会导致算法具有 O(log log n) 复杂度？直观地解释了 的来源O(log log n)： whilelog n来自每一步删除一半选项的算法，log log n来自每一步将选项减少到总数的平方根的算法！

• https://quantumalgorithmzoo.org/包含量子计算机可能感兴趣的算法列表，并且在大多数情况下，相对于经典计算机的量子加速不是严格指数的，而是超多项式的。然而，正如这个答案所希望强调的那样，这仍然是极其重要和革命性的。理解该存储库是这个答案的最初动机:-)

  还值得注意的是，我们目前并不期望量子计算机能够解决 NP 完全问题，通常也预计需要指数时间来解决。但也没有其他证据。另请参阅：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

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

• https://cstheory.stackexchange.com/questions/22588/is-it-right-to-call-2-sqrtn-exponential
• https://math.stackexchange.com/questions/55468/how-to-prove-that-exponential-grows-faster-than-polynomial
• https://en.wikipedia.org/w/index.php?title=Time_complexity&oldid=1026049783#Sub-exponential_time