-
多項式時間
鎖定
多項式時間在決定型機器上是最小的複雜度類別,且在機器模型改變時依舊強韌,且也是可在副程式組合過程中保持封閉的類別。
數學家有時把“如多項式時間長的算法”視為快速計算,相對應的是超多項式時間,表示任何多項式時間的輸入數目只要夠大,超多項式時間所需的解題時間終究會大大超過任何多項式時間的問題。指數時間(Exponential time)就是一例。
- 中文名
- 多項式時間
- 學 科
- 計算機
目錄
- 1 定義
- 2 數學描述
- 3 解釋
- 4 多項式時間的副類別[
多項式時間定義
多項式時間(英語:Polynomial time)在計算複雜度理論中,指的是一個問題的計算時間{\displaystyle m(n)}不大於問題大小{\displaystyle n}的多項式倍數。任何抽象機器都擁有一複雜度類,此類包括可於此機器以多項式時間求解的問題。
[1]
多項式時間數學描述
以數學描述的話,則可説
,此k為一常量值(依問題而定)。
數學家有時把“如多項式時間長的算法”視為快速計算,相對應的是超多項式時間,表示任何多項式時間的輸入數目只要夠大,超多項式時間所需的解題時間終究會大大超過任何多項式時間的問題。指數時間就是一例。
可以在決定型依序機器上(例如圖靈機)以多項式時間解決的決定性問題,其屬於的複雜度類被稱為P。可以在多項式時間驗證答案的決定性問題稱為NP。而NP也是可以在非確定型圖靈機以多項式時間解決的問題(NP兩字為Non-deterministicPolynomial的縮寫)。
多項式時間解釋
超多項式時間:O(c^f(n)),其中c為大於1的常數,f(n)大於常數,小於線性。
可以在決定型依序機器上(例如圖靈機)以多項式時間解決的決定性問題,其屬於的複雜度類被稱為P。可以在多項式時間驗證答案的非決定性問題稱為NP。而NP也是可以在非確定型圖靈機以多項式時間解決的問題(NP兩字為Non-deterministic Polynomial的縮寫)。
多項式時間在決定型機器上是最小的複雜度類別,且在機器模型改變時依舊強韌,且也是可在副程式組合過程中保持封閉的類別。