什么是p問題、np問題和npc問題-展示頁
2025-01-22 23:28本頁面
【正文】 效率不能衡量一個(gè)程序的好壞，而應(yīng)該看當(dāng)這個(gè)數(shù)據(jù)的規(guī)模變大到數(shù)百倍后，程序運(yùn)行時(shí)間是否還是一樣，或者也跟著慢了數(shù)百倍，或者變慢了數(shù)萬倍。還是先用幾句話簡單說明一下時(shí)間復(fù)雜度。下面的內(nèi)容都是在講什么是P問題，什么是NP問題，什么是NPC問題，你如果不是很感興趣就可以不看了。NP問題并不是那種只有搜才行的問題，NPC問題才是。你要知道，大多數(shù)人此時(shí)所說的NP問題其實(shí)都是指的NPC問題。什么是P問題、NP問題和NPC問題。以下是這七個(gè)難題。NP就是Nondeterministic Polynomial的問題，也即是多項(xiàng)式復(fù)雜程度的非確定性問題。多流水線調(diào)度實(shí)際上是一個(gè)NP完全問題這個(gè)獎(jiǎng)還沒有人拿到，也就是說，NP問題到底是Polynomial，還是NonPolynomial，尚無定論。問題就在這個(gè)問號(hào)上，到底是NP等于P，還是NP不等于P。簡單的寫法是NP=P?，問題就在這個(gè)問號(hào)上，到底是NP等于P，還是NP不等于P。什么是P問題、NP問題和NPC問題NP完全問題，是世界七大數(shù)學(xué)難題之一。NP的英文全稱是Nondeterministic Polynomial的問題，即多項(xiàng)式復(fù)雜程度的非確定性問題。數(shù)學(xué)上著名的NP問題，完整的叫法是NP完全問題，也即NP COMPLETE問題，簡單的寫法，是NP=P?的問題。證明其中之一，便可以拿百萬美元大獎(jiǎng)。NP里面的N，不是NonPolynomial的N，是NonDeterministic，P代表Polynomial倒是對(duì)的。美國麻州的克雷(Clay)數(shù)學(xué)研究所于2000年5月24日在巴黎法蘭西學(xué)院宣布了一件被媒體炒得火熱的大事：對(duì)七個(gè)千僖年數(shù)學(xué)難題的每一個(gè)懸賞一百萬美元。千僖難題之一：P(多項(xiàng)式算法)問題對(duì)NP(非多項(xiàng)式算法)問題千僖難題之二：霍奇(Hodge)猜想千僖難題之三：龐加萊(Poincare)猜想千僖難題之四：黎曼(Riemann)假設(shè)千僖難題之五：楊米爾斯(YangMills)存在性和質(zhì)量缺口千僖難題之六：納維葉斯托克斯(NavierStokes)方程的存在性與光滑性千僖難題之七：貝赫(Birch)和斯維訥通戴爾(SwinnertonDyer)猜想NP完全問題排在百萬美元大獎(jiǎng)的首位，足見他的顯赫地位和無窮魅力。你會(huì)經(jīng)常看到網(wǎng)上出現(xiàn)這怎么做，這不是NP問題嗎、這個(gè)只有搜了，這已經(jīng)被證明是NP問題了之類的話。他們沒有搞清楚NP問題和NPC問題的概念。好，行了，基本上這個(gè)誤解已經(jīng)被澄清了。接下來你可以看到，把NP問題當(dāng)成是NPC問題是一個(gè)多大的錯(cuò)誤。時(shí)間復(fù)雜度并不是表示一個(gè)程序解決問題需要花多少時(shí)間，而是當(dāng)問題規(guī)模擴(kuò)大后，程序需要的時(shí)間長度增長得有多快。不管數(shù)據(jù)有多大，程序處理花的時(shí)間始終是那么多的，我們就說這個(gè)程序很好，具有O(1)的時(shí)間復(fù)雜度，也稱常數(shù)級(jí)復(fù)雜度；數(shù)據(jù)規(guī)模變得有多大，花的時(shí)間也跟著變得有多長，這個(gè)程序的時(shí)間復(fù)雜度就是O(n)，比如找n個(gè)數(shù)中的最大值；而像冒泡排序、插入排序等，數(shù)據(jù)擴(kuò)大2倍，時(shí)間變慢4倍的，屬于O(n^2)的復(fù)雜度。不會(huì)存在O(2*n^2)的復(fù)雜度，因?yàn)榍懊娴哪莻€(gè)2是系數(shù)，根本不會(huì)影響到整個(gè)程序的時(shí)間增長。因此，我們會(huì)說，一個(gè)O(*n^3)的程序的效率比O(100*n^2)的效率低，盡管在n很小的時(shí)候，前者優(yōu)于后者，但后者時(shí)間隨數(shù)據(jù)規(guī)模增長得慢，最終O(n^3)的復(fù)雜度將遠(yuǎn)遠(yuǎn)
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1