什麼是n的最小值使得算法，其運行時間爲100N^2個的運行速度更快

什麼是n的最小值使得算法，其運行時間爲100N^2組的運行比的算法，其運行時間更快2^n在同一臺機器上？什麼是n的最小值使得算法，其運行時間爲100N^2個的運行速度更快

範圍
雖然我感興趣的答案，我更感興趣的是如何找到一步的答案步驟（這樣我就可以重複這一過程，如果在所有可能比較任意兩個給定的算法）。

來自MIT Press Algorithms的書

2014-10-17 Nate Neuhaus

這可以認爲是比'100平方米= 2m'值'M'，這可能會提醒'100平方米的大 - 2米= 0'。 – greybeard 2014-10-17 09:27:21

爲什麼你會投這個問題？問題在於瘋狂的MIT書。哇... – 2014-10-17 09:29:34

上面是誰？ stackexchange的一個（錯誤的）功能是，up-down和downvoting都不需要註釋，並且如果評論的文本沒有聲明一個（我說沒有投票），那麼沒有連接投票。 – greybeard 2014-10-17 09:34:46

這很簡單。你想要的n的值，其中100* n^2小於2n。

這是100n^2 - 2n < 0的解決方案，恰好是 0 < n < 0.02。

一千字：

enter image description here

來源

2014-10-17 10:03:18 axiom

是的，我認爲這是沿着這些線路的東西，直到先生「那麼一直」爲我提供了一個很好的小頭痛。不知道那裏發生了什麼一分鐘（哈哈）。謝謝。 – 2014-10-17 10:11:13

一張圖片就是1000字，哈哈。如果你不介意我的問題，你用什麼來生成這個漂亮的小圖片？ – 2014-10-17 10:30:23

@NateNeuhaus gnu八度。 – axiom 2014-10-17 10:34:13

，你必須知道的第一件事，就是運行時間表示。如果我們談論算法理論上，算法的運行時間是步數（或時間的量）需要根據輸入（其中輸入的大小爲例如的尺寸來完成位數，有時也考慮其他措施）。從這個意義上講，需要最少步數的算法是最快的。

所以在你的兩個公式，n是輸入的大小，以及100 * N^2和2^n是兩種算法，如果給定大小n的輸入運行的步數。

乍一看，2^N算法看起來比100 * N^2算法快得多。例如，對於n = 4，100 * 4^2 = 1600和2^4 = 16

然而，2^n是指數函數，而100 * N^2是一個多項式函數 。這意味着當n足夠大時，情況就是2^n> 100 * n^2。所以你將不得不解決100 * n^2的不平等問題。對於一個相當小的n來說，情況就是這樣，所以你可以從n = 5開始評估函數，幾分鐘後你就可以得到答案。

來源

2014-10-17 12:07:59 Hoopje

謝謝您的迴應，但是這個問題是關於實踐而不是理論。在這一點上，我正在通過本書的第一章和第二章進行練習，並且不太清楚我的答案。就數學而言，我意識到指數函數的增長速度將比線性函數增長得快得多。但是，謝謝你的時間。 – 2014-10-18 02:30:09

如果你正在做「算法」，而不是「用C++編程」，那麼你正在做理論而不是實踐。請注意，問題被回滾到錯誤的版本（線性函數2n在這種情況下沒有多大意義），並且您接受的答案會回答這個錯誤的問題。（我剛從這裏開始，並沒有足夠的聲望去做任何事情，或者對錯誤的答案發表評論。） – Hoopje 2014-10-18 07:36:15

那麼我正在用C++做算法......（等待它）！對於我的理論的一些實踐，或者說我正在練習，但僅在理論上，沃森呢？ – 2014-10-20 10:07:39

什麼是n的最小值使得算法，其運行時間爲100N^2個的運行速度更快

回答

相關問題