## 該筆記自用為主，記錄一些日常學(xué)習(xí)過程中看到的不熟悉的知識(shí)和從未接觸過的知識(shí)，用于回看和記錄。其中有一些個(gè)人理解，如有錯(cuò)誤請(qǐng)討論指正。

前言

在討論這一串問題之前，我們需要復(fù)習(xí)兩個(gè)概念。

1.多項(xiàng)式和非多項(xiàng)式

多項(xiàng)式：

非多項(xiàng)式：或者

2.時(shí)間復(fù)雜度

在計(jì)算機(jī)算法求解問題當(dāng)中，經(jīng)常用時(shí)間復(fù)雜度和空間復(fù)雜度來表示一個(gè)算法的運(yùn)行效率?？臻g復(fù)雜度表示一個(gè)算法在計(jì)算過程當(dāng)中要占用的內(nèi)存空間大小。時(shí)間復(fù)雜度則表示這個(gè)算法運(yùn)行得到想要的解所需的計(jì)算工作量。這里探討的是當(dāng)輸入值（也就是問題數(shù)目N，或者是待求解的問題）接近無窮時(shí)，算法所需工作量的變化快慢程度。

舉例：冒泡排序。

在計(jì)算機(jī)當(dāng)中，排序問題是最基礎(chǔ)的，將輸入按照大小或其他規(guī)則排好序，有利于后期運(yùn)用數(shù)據(jù)進(jìn)行其他運(yùn)算。冒泡排序就是其中的一種排序算法。假設(shè)手上現(xiàn)在有n個(gè)無序的數(shù)（N個(gè)待排序的問題），利用冒泡排序?qū)ζ溥M(jìn)行排序，

①首先比較第1個(gè)數(shù)和第2個(gè)數(shù)，如果后者>前者，就對(duì)調(diào)他們的位置，否則不變

②接著比較第2個(gè)數(shù)和第3個(gè)數(shù)，如果后者>前者，就對(duì)調(diào)他們的位置，否則不變

③一直向下比較直到第n-1和第n個(gè)數(shù)比較完，第一輪結(jié)束。（這時(shí)候最大的數(shù)移動(dòng)到了第n個(gè)數(shù)的位置）

④重復(fù)前三步，但是只比較到第n-1個(gè)數(shù)（將第二大的數(shù)移動(dòng)到第n-1個(gè)數(shù)位置）

⑤持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

舉個(gè)實(shí)例：5,4,3,2,1，對(duì)其進(jìn)行排序，先是比較5跟4變成4,5,3,2,1，第一輪結(jié)束后變成43215，可以計(jì)算，當(dāng)對(duì)其排序完正好要經(jīng)過4+3+2+1=10次比較，當(dāng)然這是最復(fù)雜的情況，即完全反序?？梢灾缹?duì)于n個(gè)數(shù)，至多要經(jīng)過1+2+...+n-1即(n^2-n)/2次比較才能排好序。這個(gè)式子里n的最高次階是2，可知道當(dāng)n→∞時(shí)，一次性對(duì)其比較次數(shù)影響很小，所以我們把這個(gè)算法的時(shí)間復(fù)雜度比作：。取其最高次，可以看出，這是一個(gè)時(shí)間復(fù)雜度為多項(xiàng)式的表示方式。

另外一些窮舉類的算法，所需時(shí)間長(zhǎng)度成幾何階數(shù)上漲，這就是的指數(shù)級(jí)復(fù)雜度，甚至的階乘級(jí)復(fù)雜度。它是非多項(xiàng)式級(jí)的，其復(fù)雜度計(jì)算機(jī)往往不能承受。

當(dāng)我們?cè)诮鉀Q一個(gè)問題時(shí)，我們選擇的算法通常都需要是多項(xiàng)式級(jí)的復(fù)雜度，非多項(xiàng)式級(jí)的復(fù)雜度需要的時(shí)間太多，往往會(huì)超時(shí)，除非是數(shù)據(jù)規(guī)模非常小。

正文

1、P問題
P問題：能夠在多項(xiàng)式時(shí)間內(nèi)被解決的問題。

比如說，給10個(gè)、20個(gè)、30個(gè)… 元素（問題）排序，復(fù)雜度是

2、NP問題
NP問題：能夠在多項(xiàng)式時(shí)間內(nèi)使用非確定性算法（non-deterministic）被解決的問題。

NP問題也可以指在多項(xiàng)式的時(shí)間里驗(yàn)證一個(gè)解的問題。另一個(gè)定義是，可以在多項(xiàng)式的時(shí)間里猜出一個(gè)解的問題。

簡(jiǎn)單來說就是，必須以非常規(guī)方法才能在多項(xiàng)式時(shí)間內(nèi)解決的問題，就叫做NP問題。

舉個(gè)例子：

我人品很好，在程序中需要枚舉時(shí)，我可以一猜一個(gè)準(zhǔn)。

現(xiàn)在某人拿到了一個(gè)求最短路徑的問題，問從起點(diǎn)到終點(diǎn)是否有一條小于100個(gè)單位長(zhǎng)度的路線。它根據(jù)數(shù)據(jù)畫好了圖，但怎么也算不出來，于是來問我：你看怎么選條路走得最少？

我說，我人品很好，肯定能隨便給你指條很短的路出來。然后我就胡亂畫了幾條線，說就這條吧。那人按我指的這條把權(quán)值加起來一看，嘿，神了，路徑長(zhǎng)度98，比100小。

于是答案出來了，存在比100小的路徑。別人會(huì)問他這題怎么做出來的，他就可以說，因?yàn)槲艺业搅艘粋€(gè)比100 小的解。在這個(gè)題中，找一個(gè)解很困難，但驗(yàn)證一個(gè)解很容易。

驗(yàn)證一個(gè)解只需要O(n)的時(shí)間復(fù)雜度，也就是說我可以花O(n)的時(shí)間把我猜的路徑的長(zhǎng)度加出來。那么，只要我運(yùn)氣好，猜得準(zhǔn)，我一定能在多項(xiàng)式的時(shí)間里解決這個(gè)問題。這就是NP問題。

3、NP-complete問題（即：NP完全問題）

NP-Complete 滿足兩個(gè)條件：

• 首先它是一個(gè)NP問題
• 所有的NP問題都可以約化（Reducible）到它，NPC問題目前沒有多項(xiàng)式的有效算法，只能用指數(shù)級(jí)甚至階乘級(jí)復(fù)雜度的搜索

約化：例如，求解一個(gè)一元一次方程 A AA 和求解一個(gè)一元二次方程 B BB，你若會(huì)求解 B BB ，你一定會(huì)求解 A AA。那么我們說，A 可以約化為 B。B BB 的時(shí)間復(fù)雜度高于或者等于 A AA的時(shí)間復(fù)雜度。

NP問題中最困難的問題稱之為NP完全問題(NP-complete)。根據(jù)庫(kù)克定理，任意一個(gè)NP完全問題如果能夠在多項(xiàng)式時(shí)間內(nèi)解決，則所有的NP問題都能在多項(xiàng)式時(shí)間內(nèi)解決。

一般來說，非常規(guī)方法既可以解決P問題，也可以解決NP問題，所以，只有用非常規(guī)方法才能解決的問題，才能叫做NP完全問題。

示例：旅行商問題。就是一個(gè)NP完全問題，因?yàn)槠溟_銷不能在多項(xiàng)式時(shí)間內(nèi)解決，而是一個(gè)非多項(xiàng)式時(shí)間復(fù)雜度的問題。

4、NP-Hard問題（即：NP難問題）
NP-Hard問題：和NP問題一樣困難，或者更加困難的問題。

NP hard 滿足 NPC 的第二條件，但不一定是 NP 問題。
因?yàn)樗灰欢ㄊ荖P問題。即使 NPC 問題發(fā)現(xiàn)了多項(xiàng)式級(jí)的算法，NP-Hard 問題有可能仍然無法得到多項(xiàng)式級(jí)的算法。事實(shí)上，由于 NP-Hard 放寬了限定條件，它將有可能比所有的 NPC 問題的時(shí)間復(fù)雜度更高從而更難以解決。

anyway,感覺對(duì)于NP-C和NP-Hard還是有一點(diǎn)點(diǎn)混淆，等下次再遇見了再來理解并修改它。

其實(shí)還有點(diǎn)想糾結(jié)一下NPC的邏輯，但是，下次再說吧

以上四個(gè)問題他們之間的關(guān)系可以用下圖來表示：?

參考鏈接：

到底什么是NP問題，NP hard問題，NP完全問題？

P問題、NP問題、NP完全問題和NP難問題

【釋義】NP complete概念淺析（涵蓋：P問題，NP問題，NP完全問題，NP難問題）文章來源地址http://www.zghlxwxcb.cn/news/detail-484307.html

到了這里，關(guān)于NP-Hard？大白話學(xué)習(xí)P問題、NP問題、NP完全問題和NP難問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！