首頁 > 資訊 > 經(jīng)驗 > 多項式時間，多項式的時間和空間是什么

多項式時間，多項式的時間和空間是什么

來源：整理時間：2024-10-10 11:36:01 編輯：智能門戶手機版

1，多項式的時間和空間是什么

時間和空間是有成比的！一個空間的存在和時間有密切關(guān)聯(lián)！

多項式的時間和空間是什么

2，多項式時間的介紹

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

多項式時間的介紹

3，多項式時間的定義

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

多項式時間的定義

4，多項式時間的解釋

數(shù)學家有時把“比多項式時間長的算法”視為快速計算，相對應的是超多項式時間，表示任何多項式時間的輸入數(shù)目只要夠大，超多項式時間所需的解題時間終究會大大超過任何多項式時間的問題。指數(shù)時間（Exponential time）就是一例。超多項式時間：O(c^f(n))，其中c為大于1的常數(shù)，f(n)大于常數(shù)，小于線性?？梢栽跊Q定型依序機器上（例如圖靈機）以多項式時間解決的決定性問題，其屬于的復雜度類被稱為P?？梢栽诙囗検綍r間驗證答案的非決定性問題稱為NP。而NP也是可以在非確定型圖靈機以多項式時間解決的問題（NP兩字為Non-deterministic Polynomial的縮寫）。多項式時間在決定型機器上是最小的復雜度類別，且在機器模型改變時依舊強韌，且也是可在副程式組合過程中保持封閉的類別。強多項式時間指的是此問題的運算時間不因輸入資料的數(shù)字大小而變動，而是依照輸入資料的結(jié)構(gòu)復雜度（例如圖中的頂點數(shù)量）。

5，急多項式時間內(nèi)算法

多項式時間就是指時間復雜度是個多項式或者說,就是這個程序運行的時間隨著數(shù)據(jù)規(guī)模n變化的函數(shù)為f(n)那么,f(n)是個多項式函數(shù),那么就可以說是控制在多項式之內(nèi).

定義：若存在一個常數(shù)c，使得對于所有n>=0，都有|f(n)| <= c*|g(n)|，則稱函數(shù)f(n)是o(g(n))。時間復雜度是o(p(n))的算法稱為多項式時間算法，這里p(n)是關(guān)于n的多項式。不能夠這樣限制時間復雜度的算法被稱為指數(shù)時間算法?！　±纾簳r間復雜度為o(nlog(n))、o(n^3)的算法都是多項式時間算法，時間復雜度為o(n^log(n))、o(n!)、o(2^n)的算法是指時間算法?！　∫粋€優(yōu)化問題如果已經(jīng)找到了多項式時間算法，則稱該問題為多項式時間可解問題，并將這類問題的集合記為p，因此多項式時間可解問題就稱為p類問題。　　一個問題如果沒有找到多項式時間算法，那么直覺上它是“難解”的，但又往往無法證明多項式時間算法的不存在性。由于在尋找有效算法上的失敗未必一定意味著這樣的算法不存在，這就給理論工作者帶來了一個難題：一方面證明一個問題不存在多項式時間算法是困難的，至今尚未給出；另一方面有越來越多的問題無法給出多項式時間算法。同時，理論工作者又渴望解決此難題。為此，在20世紀70年代提供了一個漂亮的理論，它把這種失敗歸結(jié)為一個深刻的數(shù)據(jù)猜想，這個理論就是np-完全性理論?！　《x：給定一個判定問題，如果存在一個算法，對任何一個答案為“是”的實例i。該算法首先給出一個猜想，該猜想規(guī)模不超過i的輸入長度的某個多項式函數(shù)，且驗證猜想的正確性僅需多項式時間，則稱該問題屬于np類?！　《x：如果np類中所有問題都可以多項式時間歸約到np類中某個問題x，則稱x是np-完全問題?！　《x：如果某優(yōu)化問題x的判定問題是np-完全的，則稱問題x是np-難的；如果x的判定問題是強np-完全的，則稱x是強np-難的。

6，什么是偽多項式時間算法

polynomial-timealgorithm多項式時間算法定義：若存在一個常數(shù)C，使得對于所有n>=0，都有|f(n)|<=C*|g(n)|，則稱函數(shù)f(n)是O(g(n))。時間復雜度是O(p(n))的算法稱為多項式時間算法，這里p(n)是關(guān)于n的多項式。不能夠這樣限制時間復雜度的算法被稱為指數(shù)時間算法。例如：時間復雜度為O(nlog(n))、O(n^3)的算法都是多項式時間算法，時間復雜度為O(n^log(n))、O(n!)、O(2^n)的算法是指時間算法。一個優(yōu)化問題如果已經(jīng)找到了多項式時間算法，則稱該問題為多項式時間可解問題，并將這類問題的集合記為P，因此多項式時間可解問題就稱為P類問題。一個問題如果沒有找到多項式時間算法，那么直覺上它是“難解”的，但又往往無法證明多項式時間算法的不存在性。由于在尋找有效算法上的失敗未必一定意味著這樣的算法不存在，這就給理論工作者帶來了一個難題：一方面證明一個問題不存在多項式時間算法是困難的，至今尚未給出；另一方面有越來越多的問題無法給出多項式時間算法。同時，理論工作者又渴望解決此難題。為此，在20世紀70年代提供了一個漂亮的理論，它把這種失敗歸結(jié)為一個深刻的數(shù)據(jù)猜想，這個理論就是NP-完全性理論。定義：給定一個判定問題，如果存在一個算法，對任何一個答案為“是”的實例I。該算法首先給出一個猜想，該猜想規(guī)模不超過I的輸入長度的某個多項式函數(shù)，且驗證猜想的正確性僅需多項式時間，則稱該問題屬于NP類。定義：如果NP類中所有問題都可以多項式時間歸約到NP類中某個問題x，則稱x是NP-完全問題。定義：如果某優(yōu)化問題x的判定問題是NP-完全的，則稱問題x是NP-難的；如果x的判定問題是強NP-完全的，則稱x是強NP-難的。

定義：若存在一個常數(shù)c，使得對于所有n>=0，都有|f(n)| <= c*|g(n)|，則稱函數(shù)f(n)是o(g(n))。時間復雜度是o(p(n))的算法稱為多項式時間算法，這里p(n)是關(guān)于n的多項式。不能夠這樣限制時間復雜度的算法被稱為指數(shù)時間算法。例如：時間復雜度為o(nlog(n))、o(n^3)的算法都是多項式時間算法，時間復雜度為o(n^log(n))、o(n!)、o(2^n)的算法是指時間算法。一個優(yōu)化問題如果已經(jīng)找到了多項式時間算法，則稱該問題為多項式時間可解問題，并將這類問題的集合記為p，因此多項式時間可解問題就稱為p類問題。一個問題如果沒有找到多項式時間算法，那么直覺上它是“難解”的，但又往往無法證明多項式時間算法的不存在性。由于在尋找有效算法上的失敗未必一定意味著這樣的算法不存在，這就給理論工作者帶來了一個難題：一方面證明一個問題不存在多項式時間算法是困難的，至今尚未給出；另一方面有越來越多的問題無法給出多項式時間算法。同時，理論工作者又渴望解決此難題。為此，在20世紀70年代提供了一個漂亮的理論，它把這種失敗歸結(jié)為一個深刻的數(shù)據(jù)猜想，這個理論就是np-完全性理論。定義：給定一個判定問題，如果存在一個算法，對任何一個答案為“是”的實例i。該算法首先給出一個猜想，該猜想規(guī)模不超過i的輸入長度的某個多項式函數(shù)，且驗證猜想的正確性僅需多項式時間，則稱該問題屬于np類。定義：如果np類中所有問題都可以多項式時間歸約到np類中某個問題x，則稱x是np-完全問題。定義：如果某優(yōu)化問題x的判定問題是np-完全的，則稱問題x是np-難的；如果x的判定問題是強np-完全的，則稱x是強np-難的。