查看“︁多項式時間”︁的源代码

{{noteTA
|G1=IT
}}
'''多項式時間'''（{{lang-en|Polynomial time}}）在[[計算複雜度理論]]中，指的是一個問題的計算時間<math>m(n)</math>不大於問題大小<math>n</math>的[[多項式]]倍數。任何抽象機器都擁有一[[複雜度類]]，此類包括可於此機器以多項式時間求解的問題。

以數學描述的話，則可說<math>m(n) =</math> [[大O符號|O]]<math>(n^k)</math>，此<math>k</math>為一常數值（依問題而定）。

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

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

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

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

== 多項式時間的副類別 ==

* [[常數時間]]：[[大O符號|O]](''1'')
* [[線性時間]]：[[大O符號|O]](''n'')
* 平方時間：[[大O符號|O]](''n''<sup>2</sup>)
* 立方時間：[[大O符號|O]](''n''<sup>3</sup>)
* <math>\Omicron(n\log(n))</math>

==参见==
* [[最长公共子序列]]
* [[Floyd-Warshall算法]]
* [[维特比算法|Viterbi算法]]
* [[柯爾莫哥洛夫空間]]
* [[柯氏复杂性]]

==參考文獻==
{{refbegin}}
* [https://www.nextbigfuture.com/2017/03/computing-exponentially-faster-using-dna.html Computing exponentially faster using DNA] {{Wayback|url=https://www.nextbigfuture.com/2017/03/computing-exponentially-faster-using-dna.html |date=20201112011913 }}. In: [https://www.nextbigfuture.com/ next BIG Future] {{Wayback|url=https://www.nextbigfuture.com/ |date=20210303043446 }} (Blog). 1. März 2017, abgerufen am 10. März 2017 (englisch).
{{refend}}

== 參閱 ==
{{div col|cols=2}}
*[[常數時間]]
*[[線性時間]]
*[[指數時間]]
*[[計算複雜度理論]]
*[[P/NP問題]]
*[[NP (複雜度)|NP]]
*[[演算法]]
*[[大O符號]]
{{div col end}}

[[Category:計算複雜性理論]]
[[Category:計算資源]]