O（n Log n）是多項式時間嗎？

O（n Log n）是多項式時間嗎？如果是這樣，你能解釋爲什麼嗎？O（n Log n）是多項式時間嗎？

我對數學證明很感興趣，但是我會很感激任何強大的直覺。

謝謝！

2013-11-09 Yahiko Kikikoto

它至少不比多項式時間差。而且還不是更好：n < n log n < n * n。

2013-11-09 22:36:32 Inspired

這個答案顯然是錯的！請參閱http://en.wikipedia.org/wiki/Big_O_notation， http://en.wikipedia.org/wiki/Time_complexity和 http://mathworld.wolfram.com/PolynomialTime.html –

您能否詳細說明這裏確實是錯誤的？（還要注意，在計算機科學中，Big-O經常用於Big-Theta的意義上。） – Inspired

O（n^2）仍然是多項式時間。 n

這是因爲它是由多項式（n）上界的。你可以看看圖表並從那裏去，但我不能制定一個除此之外的數學證明：P

編輯：從維基百科頁面，「算法說是多項式時間if其運行時間由算法的輸入大小中的多項式表達式限定。

來源

2013-11-09 22:41:00

-1

是的。當n走向無窮時，nlogn的限制是多少？直觀地說，對於大n，n >> logn，您可以考慮由n和nlogn〜n支配的乘積，這顯然是多項式時間。更嚴格的證據是通過使用Inspired做出的夾心定理：

n^1 < nlogn < n^2。

因此，nlogn在多項式時間的序列的上方（和下方）是有界的。

來源

2013-11-09 22:44:02 user1654183

我沒有說它是1，如果我們是迂腐的，我們可以說n在n無窮大時會支配nlogn的極限。嚴格來說，趨於無限的序列發散。如果你有兩個函數f（n）* g（n），那麼極限，如果乘積是lim f（n）* lim g（n），在這種情況下是無窮大*無窮大，這是不確定的。 – user1654183

「當n變爲無窮大時，nlogn的極限」是「n是n^1」。你能否再解釋一下這個陳述呢？ – Teepeemm

我已經做過。重複一遍：當n變爲無窮大時，n >> logn。因此，當n變爲無窮大時，基本上可以忽略logn對nlogn的貢獻，只剩下n。這不是「嚴格的」，但是這個人要求直覺...... – user1654183

是的，O（nlogn）是多項式時間。

從http://mathworld.wolfram.com/PolynomialTime.html：

的算法被認爲是在多項式時間解當來完成算法對於給定的輸入所需的步驟數是爲O（n^M）的一些非負整數m，其中n是輸入的複雜度。

從http://en.wikipedia.org/wiki/Big_O_notation：

f是O（克）當且僅當

我現在將證明是n日誌n是O（N ^米）的一些這意味着n log n是多項式時間。

確實，取m = 2。（這意味着我將證明n log n是O（n^2））

對於證明，取k = 2。（這可能會更小，但不一定要這樣。）存在一個n_0，因此對於所有較大的n，以下都成立。

N_0 * F（N）< = G（N）* k個

採取N_0 = 1（這是足夠的）現在是易見

的n logÑ< = 2 * ñ

爲log N < = 2n個

N> 0（假設）

點擊here如果你不確定這一點。

這個證明可能在乳膠數學模式中好很多，但我不認爲stackoverflow支持這一點。

來源

2013-11-09 22:47:41

如何證明'log n <= 2n'？ :) – Inspired

1.那個'n_0'不應該在那裏。爲了證明'logn <2n'，我會證明'logn

O（n Log n）是多項式時間嗎？

回答

相關問題