多项式时间
以多項式速率增長的算法的時間 / 维基百科,自由的 encyclopedia
多项式时间(英语:Polynomial time)在计算复杂度理论中,指的是一个问题的计算时间不大于问题大小的多项式倍数。任何抽象机器都拥有一复杂度类,此类包括可于此机器以多项式时间求解的问题。
以数学描述的话,则可说 O,此为一常数值(依问题而定)。
数学家有时把“如多项式时间长的演算法”视为快速计算,相对应的是超多项式时间,表示任何多项式时间的输入数目只要够大,超多项式时间所需的解题时间终究会大大超过任何多项式时间的问题。指数时间就是一例。
可以在决定型依序机器上(例如图灵机)以多项式时间解决的决定性问题,其属于的复杂度类被称为P。可以在多项式时间验证答案的决定性问题称为NP。而NP也是可以在非确定型图灵机以多项式时间解决的问题(NP两字为Non-deterministic Polynomial的缩写)。
多项式时间在决定型机器上是最小的复杂度类别,且在机器模型改变时依旧强韧,且也是可在副程式组合过程中保持封闭的类别。