多项式时间和指数时间

有人可以解释多项式时间算法，非多项式时间算法和指数时间算法之间的区别吗？

例如，如果算法花费O（n ^ 2）时间，那么它属于哪个类别？

检查这个出来。

指数比多项式差。

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非常大。就像，宇宙中的每个粒子都必须每秒进行1000亿亿次运算，而这要花费数万亿亿亿年。

我没有计算出来，但是它很大。