杂谈:什么是多项式时间

在面对各个各个算法的时候，我们常常常常见到“多项式时间”这个标准。

多项式都知道哇，$\sum_{i=0}^{n}{a_ix_i^n}$

我们就把多项式记为P(n)

那么倘若求解一个问题，需要进行的操作次数满足：$T(n) = O(P(n))$,这里多项式P(n)就刻画了求解这一问题的时间复杂度,

我们也称这一问题可以在多项式时间内完成

哎那我们怎么就逮着多项式不放呢？为什么不说指数时间、阶乘时间呢

从高中数学里函数增长的快慢我们很容易理解，当n足够大的时候，指数时间算法的步数计算机已经撑不住哩~ 阶乘更不用说

$n^k$显然比$k^n（k \not=1）$增长的慢的多。

我们把各个时间拉一张表出来：

函数类型	示例（n=10）	示例（n=30）	示例（n=50）	实际可行性
常数时间	10
线性时间（n）	10
线性对数时间(nlogn)
多项式时间（$n^3$）	1000
指数时间（$2^n$）	1024
阶乘时间（n!）	$3.6×10^6$

​