多項式時間

多項式時間（英語：Polynomial time）在計算複雜度理論中，指的是一個問題的計算時間${\displaystyle m(n)}$不大於問題大小${\displaystyle n}$的多項式倍數。任何抽象機器都擁有一複雜度類，此類包括可於此機器以多項式時間求解的問題。

以數學描述的話，則可說${\displaystyle m(n)=}$ O${\displaystyle (n^{k})}$，此${\displaystyle k}$為一常數值（依問題而定）。

數學家有時把「如多項式時間長的演算法」視為快速計算，相對應的是超多項式時間，表示任何多項式時間的輸入數目只要夠大，超多項式時間所需的解題時間終究會大大超過任何多項式時間的問題。指數時間就是一例。

可以在決定型依序機器上（例如圖靈機）以多項式時間解決的決定性問題，其屬於的複雜度類被稱為P。可以在多項式時間驗證答案的決定性問題稱為NP。而NP也是可以在非確定型圖靈機以多項式時間解決的問題（NP兩字為Non-deterministic Polynomial的縮寫）。

多項式時間在決定型機器上是最小的複雜度類別，且在機器模型改變時依舊強韌，且也是可在副程式組合過程中保持封閉的類別。

強多項式時間指的是此問題的運算時間不因輸入資料的數字大小而變動，而是依照輸入資料的結構複雜度（例如图论中的頂點數量）。

多項式時間的副類別

• 常數時間：O(1)
• 線性時間：O(n)
• 平方時間：O(n²)
• 立方時間：O(n³)
• ${\displaystyle \mathrm {O} (n\log(n))}$

参见

• 最长公共子序列
• Floyd-Warshall算法
• Viterbi算法
• 柯爾莫哥洛夫空間
• 柯氏复杂性

參考文獻

• Computing exponentially faster using DNA （页面存档备份，存于互联网档案馆）. In: next BIG Future （页面存档备份，存于互联网档案馆） (Blog). 1. März 2017, abgerufen am 10. März 2017 (englisch).

參閱

• 常數時間
• 線性時間
• 指數時間
• 計算複雜度理論
• P/NP問題
• NP
• 演算法
• 大O符號