多项式时间和指数时间

我有一个关于多项式时间algorithm，非多项式时间algorithm和指数时间algorithm之间的区别的问题，例如，如果一个algorithm将花费O（n ^ 2）时间，那么它将处于哪个类别？

Answer 1

看一下这个

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

指数比多项式差。

O（n ^ 2）属于二次型，它是一种多项式（指数等于2的特例），比指数式好。

指数比多项式要糟糕得多。 看看function如何增长

n = 10 | 100 | 1000 n^2 = 100 | 10000 | 1000000 k^n = k^10 | k^100 | k^1000 

k ^ 1000是非常巨大的，除非k小于1.1。 就像宇宙中的每一个粒子一样，为了完成这个任务，每秒钟要做上千亿亿次的运算。

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

Answer 2

下面是一些常见的Big-Ofunction，同时分析algorithm。

• O（ 1 ） – 恒定的时间
• O（ log（n） ） – 对数时间
• O（ （log（n）） ^c ） – polylogarithmic时间
• O（ n ） – 线性时间
• O（ n ² ） – 二次时间
• O（ n ^c ） – 多项式时间
• O（ c ⁿ ） – 指数时间

（n =input的大小，c =一些常数）

这里是代表一些函数的大O复杂性的模型图

欢呼声:-)

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

Answer 3

O（n ^ 2）是多项式时间。 多项式是f（n）= n ^ 2。 另一方面，O（2 ^ n）是指数时间，其中指数函数隐含的是f（n）= 2 ^ n。 不同之处在于n的函数是将n放在幂乘的基础上还是指数本身。

任何指数增长函数都将比任何多项式函数增长得更快（长期），所以区别与algorithm的效率有关，特别是对于大的n值。

Answer 4

多项式时间。

多项式是类似于Constant * x^k的术语的线性组合。在相反的情况下，指数意味着类似于k^x ，其中在这两种情况下，k是常数，而x是variables。

指数algorithm的执行时间比多项式的执行时间要快得多。

Answer 5

指数 （如果MINIMAL ONE EXPONENT取决于参数，则您有一个指数函数）：

• 例如f（x）=常数^ x

多项式 （如果NO EXPONENT取决于某些函数参数，则您有一个多项式函数）：

• 例如f（x）= x ^常量

Answer 6

多项式时间O（n）^ k表示操作次数与input大小的功率k成比例

指数时间O（k）^ n表示操作次数与input大小的指数成正比

Answer 7

o（n sequre）是多项式时间复杂度，而o（2 ^ n）是指数时间复杂度，如果p = np时最好情况下，在最坏情况下p = np不等于因为input大小n增长太长或input大小增加更长的时间去处理最坏的情况，处理如此复杂的增长率增长，并且取决于input小时的n个input大小，当input大小大和大时是多个，所以p = np不等于它意味着增长率取决于input的大小。 ”。 优化，坐，集团和独立集也满足指数多项。