能否用通俗的語言解釋多項式時間？

1樓：

知乎首答。舉乙個中學生應該都能聽懂的例子。

假設你被關在乙個房間裡，房間有一扇門，門上有一些開關，假設是個。你必須將一定數量的開關按下去才能把門開啟出去，事先不知道是多少個。現在請問你要花多長時間才能出去？

你別無選擇，只能乙個個試。答案很明顯，正比於房門上的開關數目，對吧？所以這個問題的計算時間可以表示為，這裡房門上的開關數目n就是問題的規模，次數為1。

現在你出去了，又發現了一扇一模一樣的門，那麼你還要再花大致一樣的時間才能開啟。對於兩扇門而言你走出去所需要的總時間大約為，2就是多項式倍數，次數仍是1，因此解開兩扇門時間複雜度還是。

事實上，無論有多少扇一模一樣的門，只要開啟的原理不變，你所花費的總時間只會乘以乙個係數（就是所謂的多項式倍數），換句話說就是成線性增長的。這就是次數為1（線性）的含義；或者，增加門上的開關數量，哪怕增加一倍甚至幾倍，你只要耐心一點，最終還是能出去的。

這回你終於遇到了一扇不一樣的門。這個門被分為兩部分，每一部分上都有個開關。你必須在每一部分上都按下特定數量的開關，才能開啟門出去。

要開啟這扇門，你大約需要花費的時間，可表示為。雖然看起來很久，但這仍屬於多項式時間。

以此類推，如果門分為3部分（每一部分都有個開關），就需要的時間；分為部分，就需要的時間。無論多少部分都屬於多項式時間，表示為。注意，指數項是個常數，和無關（和門被分割成的部分數目有關，和每部分上的開關數目無關）。

這裡稍微解釋一下多項式時間，多項式你總知道吧？形如：

的式子稱為關於的次多項式。只要問題的計算時間相對於問題大小可以表示為這樣的形式，這個問題就屬於多項式時間問題。我們在考慮計算複雜度時，只關注它的最高次項而將其他低次項以及各項前的係數都忽略掉，記為。

我們將所有此類問題都歸為乙個大類，P問題。

為什麼這個「多項式時間」那麼重要而且經常提到？因為它是當今計算科學裡，問題「可解」與「不可解」的分水嶺。理論上，只要此問題屬於P之一大類，目前的計算機都能在可接受的時間內找到問題的最優解；實際上，當指數係數很大時最優解的尋找也會很困難，但無論如何理論上是可行的。

反之，如果計算時間不能表述為這樣的形式，我們就將其歸為NP問題（非多項式時間）。注意我這裡說的「不可解」不是說問題完全無法求解，實際上大部分NP問題，要找到可行解相當容易，但是最優解卻幾乎無法在可接受的時間內找到。

此外還有一類問題稱為NP困難問題，基於現有理論，幾乎是肯定不能在多項式時間內進行求解的。下面我們接著開門。

再開了無數扇門以後你遇到了這樣一扇門，它上面的開關按下後可以重新撥上去。只有某種特定的開關組合才能把門開啟。現在讓我們來算一下你需要多長時間開門：

每乙個開關有撥上去或者按下去兩種狀態，那麼總共有種狀態。假設你把所有開關撥動到每一種狀態的時間都差不多，那麼總時間就可以表述為，也就是指數時間。指數時間是乙個可怕的敵人。

為什麼？假設你按下除錯所有開關到某個狀態需要10秒，如果一共有5個開關，那麼你需要320秒試完所有的可能。如果把開關數增加到6個，那麼需要的時間將翻一倍到640秒，13個就是81920秒，將近一天的時間。

還不夠可怕嗎？繼續增加，增加到22個，你就需要一年多的時間；增加到28個，你一輩子都會困在這個房間裡。感受到被指數支配的恐懼了嗎？

別說是乙個人，哪怕天河二號都無法承受這麼恐怖的運算時間增幅。

不過，你以為這就是最可怕的情形了嗎？你太天真了。

假設你運氣好不小心試出了開門的開關組合，下面這個終極Boss才會要了你的命：

你需要按照某種特定的順序把所有的開關都按一遍，然後才能開門。這個問題的時間複雜度是，階乘，乙個比指數更可怕的敵人。

其實上面還有更厲害的。怪物多得是。只是，解決這種複雜問題已經不屬於人的領域了。

有的朋友也許會問，量子計算機能搞定NP問題嗎？我的答案是，我也不知道。不過就以上的例子而言，量子計算是可以開啟指數的大門的，你可以理解為，具有個量子位元的計算機，就同時有個小夥伴在同時幫你嘗試各種組合；至於階乘，大概不行，階乘除以指數還是階乘。

扯遠了，今天就到這。

2樓：趙磊

不是指數級的複雜度一般都可以叫多項式時間。

比如乙個問題輸入有n項，如果解決時間為n^2或n^3乃至n^100000000，那麼就可以叫多項式時間，但是如果要用2^n的時間，那麼就不能叫多項式時間了(叫指數時間？我不知道。)

能否用通俗的語言解釋 多項式時間 ？