多項式時間?

什麼叫多項式時間算法 10分

定義：若存在一個常數C，使得對於所有n>=0，都有|f(n)| <= C*|g(n)|，則稱函數f(n)是O(g(n))。時間複雜度是O(p(n))的算法稱為多項式時間算法，這裡p(n)是關於n的多項式。不能夠這樣限制時間複雜度的算法被稱為指數時間算法。

例如：時間複雜度為O(nlog(n))、O(n^3)的算法都是多項式時間算法，時間複雜度為O(n^log(n))、O(n!)、O(2^n)的算法是指時間算法。

一個優化問題如果已經找到了多項式時間算法，則稱該問題為多項式時間可解問題，並將這類問題的集合記為P，因此多項式時間可解問題就稱為P類問題。

一個問題如果沒有找到多項式時間算法，那麼直覺上它是“難解”的，但又往往無法證明多項式時間算法的不存在性。由於在尋找有效算法上的失敗未必一定意味著這樣的算法不存在，這就給理論工作者帶來了一個難題：一方面證明一個問題不存在多項式時間算法是困難的，至今尚未給出；另一方面有越來越多的問題無法給出多項式時間算法。同時，理論工作者又渴望解決此難題。為此，在20世紀70年代提供了一個漂亮的理論，它把這種失敗歸結為一個深刻的數據猜想，這個理論就是NP-完全性理論。

定義：給定一個判定問題，如果存在一個算法，對任何一個答案為“是”的實例I。該算法首先給出一個猜想，該猜想規模不超過I的輸入長度的某個多項式函數，且驗證猜想的正確性僅需多項式時間，則稱該問題屬於NP類。

定義：如果NP類中所有問題都可以多項式時間歸約到NP類中某個問題x，則稱x是NP-完全問題。

定義：如果某優化問題x的判定問題是NP-完全的，則稱問題x是NP-難的；如果x的判定問題是強NP-完全的，則儲x是強NP-難的。

多項式時間的定義

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

多項式時間 什麼是多項式時間

就是算法消耗的時間，與規模n呈多項式（O(n^k)）的關係

什麼是概率多項式時間

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

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

超多項式時間：O(c^f(n))，其中暢為大於1的常數，f(n)大於常數，小於線性。

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

多項式時間的介紹

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

什麼是多項式時間內可解的問題，舉個例子說明

多項式時間，就是所需時間是規模的多項式函數，典型的例子是

1次函數f(n)=kn+b

什麼是偽多項式時間算法

想要理解“偽多項式時間”，我們需要先給出“多項式時間”的一個清楚的定義。

對於“多項式時間”，我們的直觀概念是時間複雜度,其中是一常數。比如，選擇排序的時間複雜度是，是多項式時間；暴力解決TSP問題的時間複雜度是，不是多項式時間。我們稱這種時間複雜度為“傳統時間複雜度”。

我們通常認為傳統時間複雜度中的變量表示數據的輸入規模。比如，選擇排序中，指待排序數組中元素的個數；TSP問題中表示圖中節點的數量。但是，這些所謂的輸入規模，僅僅是直觀的定義，並不足夠嚴謹。為了標準化這些，在計算標準時間複雜度時，我們給出了輸入規模的標準定義：

一個問題的輸入規模是保存輸入數據所需要的bit位數。

比如，如果排序算法的輸入是一個32-bit整數 數組，那麼輸入規模就是，是指數組中元素的個數。對於一個帶有個節點、條邊的圖，需要的bit位數就是。

瞭解了輸入規模的定義，我們來看“多項式時間”的標準定義：

對於一個問題，在輸入規模為x的情況下，如果一個算法能夠在O()時間內解決此問題，則我們稱此算法是多項式時間的，其中為一常數。

當我們處理一些圖論、鏈表、數組、樹等問題時，這個標準定義下的多項式時間和我們傳統的多項式時間相差無幾。比如，用選擇排序對元素個數為的數組進行排序時，傳統時間複雜度為。輸入規模，因此，得到的標準時間複雜度是，仍然是多項式時間。

類似的，假設在帶有個節點、條邊的圖中做DFS(深度優先搜索)，傳統時間複雜度為。數據規模，因此，標準時間複雜度是，仍是多項式時間的。

然而，當我們處理一些與數論有關的問題時，事情就不太樂觀了。現在我們來討論判斷一個整數是否為素數的算法，下面是一個簡單的算法：

function isPrime(n):

for i from 2 to n - 1:

if (n mod i) = 0, return false

return true

顯然，這個算法在傳統時間複雜度計算方法中是多項式時間的。我們不妨認為它的傳統時間複雜度是。然後我們再來分析這個問題的輸入規模，可能有的同學會說，對於32-bit整數，這個輸入規模不就是32嗎？這話雖然沒錯，但是因為在這個問題中，輸入規模完全依賴於的大小，所以的範圍不再限制在32-bit整數的範圍內，而是要探討當更大時對數據規模的影響。我們知道，保存一個整數所需要的bit位數，因此，在標準的時間複雜度中，此算法的複雜度變為了!這已經不再是多項式時間，而是一個指數時間。

我們可以從下面這個例子中直觀感受一下這種指數時間的增長速度：

對於一個二進制串：

10001010101011

我們記指數時間複雜度算法運行時間為T。

然後，我們在二進制串後面僅僅增加一位：

100010101010111

這時，算法運行時間會變為2T(至少)！因此，我們僅僅增加幾個bit 就會使得算法運行時間成倍成倍的增長。