如何將算法複雜度轉換爲計算所需的時間

Question

如果我知道算法的複雜性，我能預測它在現實生活中計算多長時間嗎？

多一點背景： 我一直在試圖解決大學任務，它必須從給定的位置中找到最好的結果。我寫了一個算法，它的工作原理非常緩慢。複雜性是O(n)=5^n。對於24個元素，它計算幾分鐘。我不確定是因爲我的實現是錯誤的，還是因爲這個算法非常慢。有沒有辦法讓我估計算法應該花費多少時間？

Answer 1

最壞的情況下，你可以基於推斷。因此，在算法複雜度上，如果有N = 1,2,3,4個元素（越多越好）和O-notation估計，您可以估計任意有限數的時間。另一個問題是，隨着N的增加，這種估計精度越來越低。

你可以用它做什麼？搜索這種方法的誤差估計算法。在實踐中，它通常會給出足夠好的結果。

另外請不要忘記模型的充分性檢查。因此，對於N = 1..10和O-notation複雜性的結果，您應該檢查結果與您的O模型相關的「有多好」（如果您可以選擇符合您的結果的O-notation公式的數字）。如果你無法獲得數字，你需要更多的數字才能獲得更廣泛的圖片或......好的，你可能有錯誤的複雜度估計:-)。

相關鏈接：

• Brief review on algorithm complexity.
• Time complexity catalogue
• Really good point to start - 尋找基於代碼輸入的例子。

Answer 2

單靠時間複雜性無法預測運行時間。涉及的因素很多：硬件速度，編程語言，實現細節等。當輸入大小增加時，預計使用複雜性的唯一預計時間會增加。例如，我個人認爲O（N^2）算法比O（N^3）算法需要更長的時間，特別是對於N值小的情況，例如在你的情況下。順便說一句，5^24是一個很大的數字（5.9e16）。如果在超級計算機上花費了幾個小時，我不會感到驚訝，更不用說在我們大多數人使用的一些中檔個人電腦上。