多項式時間：

? ? ? ? ?先說一下時間復雜度，時間復雜度并不是表示一個程序解決問題需要花多少時間，而是當問題規模擴大后，程序需要的時間長度增長得有多快。也就是說，對于高速處理數據的計算機來說，處理某一個特定數據的效率不能衡量一個程序的好壞，而應該看當這個數據的規模變大到數百倍后，程序運行時間是否還是一樣，或者也跟著慢了數百倍，或者變慢了數萬倍。

? ? ? ? 在時間復雜度的計算中常用的時間復雜度按照耗費的時間從小到大依次是：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2?)<O(n!)。不管數據有多大，程序處理花的時間始終是那么多的，我們就說這個程序很好，具有O(1)的時間復雜度，也稱常數級復雜度；數據規模變得有多大，花的時間也跟著變得有多長，這個程序的時間復雜度就是O(n)，比如找n個數中的最大值；而像冒泡排序、插入排序等，數據擴大2倍，時間變慢4倍的，屬于O(n^2)的復雜度。還有一些窮舉類的算法，所需時間長度成幾何階數上漲，這就是O(a^n)的指數級復雜度，甚至O(n!)的階乘級復雜度。不會存在O(2*n^2)的復雜度，因為前面的那個“2”是系數，根本不會影響到整個程序的時間增長。同樣地，O (n^3+n^2)的復雜度也就是O(n^3)的復雜度。

? ? ? ? ?只要算法的復雜度不會是最后兩個指數或者階乘型，前面的O(1)到O(n^m)（m為常數）任意組合都算是多項式級的復雜度，它們的規模n都出現在底數位置；而O(2?)，O(n!)型 復雜度，就是非多項式級的，問題規模較大時，計算機也很難算出結果。所以我們一般會選擇多項式級復雜度的算法。

P問題：

? ? ? ?P問題：只要問題存在確定性多項式級復雜度的解決算法，就稱之為P問題。

NP問題：

? ? ? ?NP問題：不存在確定性多項式級復雜度的解決算法，但是存在多項式時間的算法來驗證某個答案是否正確，就稱之為NP問題。

? ? ? ? P問題和NP問題區別，P問題可以在多項式時間內求解，例如3x=15，我們可以得出精確的解x=5，O（x）時間復雜度；而NP問題呢，哈希函數Hash（x）=aswindhkfuil，在多項式時間內，我們雖然無法求解x，但是如果有人說他知道x，他把x=iisdfsdfw給你，你可以用x=iisdfsdfw帶入Hsah進行驗證是否正確，而驗證的時間復雜度O（1）；

? ? ? ? ?P類問題是NP問題的一個子集。也就是說，能多項式時間地解決一個問題，必然能多項式時間地驗證一個問題的解。那是否所有的NP問題都是P類問題，一個總的趨勢和大方向是人們普遍認為，P=NP不成立，也就是說，多數人相信，存在至少一個不可能有多項式級復雜度的算法的NP問題。

NP-C問題：

?? ? ? ?NPC問題的定義非常簡單。同時滿足下面兩個條件的問題就是NPC問題。首先，它得是一個NP問題；然后，所有的NP問題都可以約化到它。證明一個問題是 NPC問題也很簡單。先證明它至少是一個NP問題，再證明其中一個已知的NPC問題能約化到它（由約化的傳遞性，則NPC問題定義的第二條也得以滿足；至于第一個NPC問題是怎么來的，下文將介紹），這樣就可以說它是NPC問題了。

? ? ? ??既然所有的NP問題都能約化成NPC問題，那么只要任意一個NPC問題找到了一個多項式的算法，那么所有的NP問題都能用這個算法解決了，NP也就等于P 了。因此，給NPC找一個多項式算法太不可思議了。因此，前文才說，“正是NPC問題的存在，使人們相信P≠NP”。我們可以就此直觀地理解，NPC問題目前沒有多項式的有效算法，只能用指數級甚至階乘級復雜度的搜索。

約化(Reducibility，有的資料上叫“歸約”，簡單地說，一個問題A可以約化為問題B的含義即是，可以用問題B的解法解決問題A，或者說，問題A可以“變成”問題B。

NP-H問題：

? ? ? ??NP-Hard問題是這樣一種問題，它滿足NPC問題定義的第二條但不一定要滿足第一條（就是說，NP-Hard問題要比 NPC問題的范圍廣）。NP-Hard問題同樣難以找到多項式的算法，但它不列入我們的研究范圍，因為它不一定是NP問題。即使NPC問題發現了多項式級的算法，NP-Hard問題有可能仍然無法得到多項式級的算法。事實上，由于NP-Hard放寬了限定條件，它將有可能比所有的NPC問題的時間復雜度更高從而更難以解決。

? ? ? ??

總結

以上是生活随笔為你收集整理的P问题、NP问题、NPC问题、多项式时间的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。