什么是p問(wèn)題、np問(wèn)題和npc問(wèn)題(已修改)
2025-08-17 18:58 本頁(yè)面
【正文】 什么是P問(wèn)題、NP問(wèn)題和NPC問(wèn)題 Program Impossible | 20060828 22:58| 71 Comments | 本文內(nèi)容遵從CC版權(quán)協(xié)議 這或許是眾多OIer最大的誤區(qū)之一。你會(huì)經(jīng)常看到網(wǎng)上出現(xiàn)“這怎么做，這不是NP問(wèn)題嗎”、“這個(gè)只有搜了，這已 經(jīng)被證明是NP問(wèn)題了”之類(lèi)的話。你要知道，大多數(shù)人此時(shí)所說(shuō)的NP問(wèn)題其實(shí)都是指的NPC問(wèn)題。他們沒(méi)有搞清楚NP問(wèn)題和NPC問(wèn)題的概念。NP問(wèn)題并 不是那種“只有搜才行”的問(wèn)題，NPC問(wèn)題才是。好，行了，基本上這個(gè)誤解已經(jīng)被澄清了。下面的內(nèi)容都是在講什么是P問(wèn)題，什么是NP問(wèn)題，什么是NPC 問(wèn)題，你如果不是很感興趣就可以不看了。接下來(lái)你可以看到，把NP問(wèn)題當(dāng)成是 NPC問(wèn)題是一個(gè)多大的錯(cuò)誤。還是先用幾句話簡(jiǎn)單 說(shuō)明一下時(shí)間復(fù)雜度。時(shí)間復(fù)雜度并不是表示一個(gè)程序解決問(wèn)題需要花多少時(shí)間，而是當(dāng)問(wèn)題規(guī)模擴(kuò)大后，程序需要的時(shí)間長(zhǎng)度增長(zhǎng)得有多快。也就是說(shuō)，對(duì)于高速 處理數(shù)據(jù)的計(jì)算機(jī)來(lái)說(shuō)，處理某一個(gè)特定數(shù)據(jù)的效率不能衡量一個(gè)程序的好壞，而應(yīng)該看當(dāng)這個(gè)數(shù)據(jù)的規(guī)模變大到數(shù)百倍后，程序運(yùn)行時(shí)間是否還是一樣，或者也跟 著慢了數(shù)百倍，或者變慢了數(shù)萬(wàn)倍。不管數(shù)據(jù)有多大，程序處理花的時(shí)間始終是那么多的，我們就說(shuō)這個(gè)程序很好，具有O(1)的時(shí)間復(fù)雜度，也稱常數(shù)級(jí)復(fù)雜 度；數(shù)據(jù)規(guī)模變得有多大，花的時(shí)間也跟著變得有多長(zhǎng)，這個(gè)程序的時(shí)間復(fù)雜度就是O(n)，比如找n個(gè)數(shù)中的最大值；而像冒泡排序、插入排序等，數(shù)據(jù)擴(kuò)大2 倍，時(shí)間變慢4倍的，屬于O(n^2)的復(fù)雜度。還有一些窮舉類(lèi)的算法，所需時(shí)間長(zhǎng)度成幾何階數(shù)上漲，這就是O(a^n)的指數(shù)級(jí)復(fù)雜度，甚至O(n!) 的階乘級(jí)復(fù)雜度。不會(huì)存在O(2*n^2)的復(fù)雜度，因?yàn)榍懊娴哪莻€(gè)“2”是系數(shù)，根本不會(huì)影響到整個(gè)程序的時(shí)間增長(zhǎng)。同樣地，O (n^3+n^2)的復(fù)雜度也就是O(n^3)的復(fù)雜度。因此，我們會(huì)說(shuō)，一個(gè)O(*n^3)的程序的效率比O(100*n^2)的效率低，盡管 在n很小的時(shí)候，前者優(yōu)于后者，但后者時(shí)間隨數(shù)據(jù)規(guī)模增長(zhǎng)得慢，最終O(n^3)的復(fù)雜度將遠(yuǎn)遠(yuǎn)超過(guò)O(n^2)。我們也說(shuō)，O(n^100)的復(fù)雜度小 于O(^n)的復(fù)雜度。容易看出，前面的幾類(lèi)復(fù)雜度被分為兩種級(jí)別，其中后者的復(fù)雜度無(wú)論如何都遠(yuǎn)遠(yuǎn)大于前者：一種是 O(1),O(log(n)),O(n^a)等，我們把它叫做多項(xiàng)式級(jí)的復(fù)雜度，因?yàn)樗囊?guī)模n出現(xiàn)在底數(shù)的位置；另一種是O(a^n)和O(n!)型復(fù) 雜度，它是非多項(xiàng)式級(jí)的，其復(fù)雜度計(jì)算機(jī)往往不能承受。當(dāng)我們?cè)诮鉀Q一個(gè)問(wèn)題時(shí)，我們選擇的算法通常都需要是多項(xiàng)式級(jí)的復(fù)雜度，非多項(xiàng)式級(jí)的復(fù)雜度需要的 時(shí)間太多，往往會(huì)超時(shí)，除非是數(shù)據(jù)規(guī)模非常小。自然地，人們會(huì)想到一個(gè)問(wèn)題：會(huì)不會(huì)所有的問(wèn)題都可以找到復(fù)雜度為多項(xiàng)式級(jí)的算法呢？很遺憾，答案是否定的。有些問(wèn)題甚至根本不可能找到一個(gè)正確的算法來(lái)，這稱之為“不可解問(wèn)題”(Undecidable Decision Problem)。The Halting Problem就 是一個(gè)著名的不可解問(wèn)題，在我的Blog上有過(guò)專門(mén)的介紹和證明。再比如，輸出從1到n這n個(gè)數(shù)的全排列。不管你用什么方法，你的復(fù)雜度都是階乘級(jí)，因?yàn)?你總得用階乘級(jí)的時(shí)間打印出結(jié)果來(lái)。有人說(shuō)，這樣的“問(wèn)題”不是一個(gè)“正規(guī)”的問(wèn)題，正規(guī)的問(wèn)題是讓程序解決一個(gè)問(wèn)題，輸出一個(gè)“YES”或“NO”（這 被稱為判定性問(wèn)題），或者一個(gè)什么什么的最優(yōu)值（這被稱為最優(yōu)化問(wèn)題）。那么，根據(jù)這個(gè)定義，我也能舉出一個(gè)不大可能會(huì)有多項(xiàng)式級(jí)算法的問(wèn)題 來(lái)：Hamilton回路。問(wèn)題是這樣的：給你一個(gè)圖，問(wèn)你能否找到一條經(jīng)過(guò)每個(gè)頂點(diǎn)一次且恰好一次（不遺漏也不重復(fù)）最后又走回來(lái)的路（滿足這個(gè)條件的 路徑叫做Hamilton回路）。這個(gè)問(wèn)題現(xiàn)在還沒(méi)有找到多項(xiàng)式級(jí)的算法。事實(shí)
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1