1
從我的教科書：爲什麼我們不能使用O-Notation來比較算法？
O形符號和複雜算法的
重要的是不要試圖讓使用O型符號算法 之間的比較是很重要的。例如，假設算法A1和A2都解決了相同的問題，A1的複雜度爲O（n^3），A2的複雜度爲O（n^2）。
上述說法完全合理。
注意到我們不能斷定A2在 這種情況下比A1更有效！
爲什麼不呢？ A2的複雜度比A1慢。
A
回答
3
增長慢並不意味着絕對更快。
你是否有過這樣的經歷：你年輕的時候你的朋友比你高，但是你最終會成爲你們之間的高個子，或者相反呢？
這是一樣的意思。 A1可能更適合並且快速地解決小規模問題。遇到大問題時它會變慢。
如果你想知道更多關於數學背景的細節，那麼強烈推薦Robert Sedgewick的「An Introduction to the Analysis of Algorithms」。
1
在大O符號中有一個（未指定的）常量值。所以，你實際上是被要求 - 這幾更高效：
A1 = O(n^3) * n*K1
A2 = O(n^2) * n*K2
不知道K1和K2的值，這是很難說的A1和A2的具體運行時間。我們知道A1的曲線最終會大於A2的曲線，但我們不知道n的值是多少。
對於A1和A2還有一個潛在的常量建立時間，可能需要考慮。
A1 = O(n^3) * n*K1 + C1
A2 = O(n^2) * n*K2 + C2
+0
對於任何a，b，c，d，O（n^3）包括a * n^3 + b * n^2 + c * n + d'。這不僅僅是一個線性增加。 （它也可以包含'log n'和其他許多東西，但'a'（內部循環時間）通常是最重要的。） – rici 2014-09-21 23:15:12
+1
如果添加短語「as n n grow up without bounds」 「或」當n接近無窮大「。關鍵是，對於較小的n值，具有較高複雜度但較低設置和每操作時間的算法可能更有效。 – 2014-09-21 23:50:36
2
首先，馬克哈里森指出，有不明確的常數因素。
其次，這些是上限。對於每個a> 0，日誌n是O（n^a）。可能O（n^3）算法在每一種情況下比O（n^2）算法實際上更快，O（n^3）算法並不是最好的邊界。如果您想指定下限，請使用omega或theta符號。
第三，算法複雜度通常是對最壞情況性能的估計。您可能會對平均表現感興趣，或者採取其他措施。
有些人走得太遠，也許是出於對No Free Lunch Theorem的誤解，並指出沒有算法比任何其他更好的。如常識所示，在您選擇的任何環境中，某些算法比其他算法更好。如果您瞭解上述注意事項，則計算複雜性界限可能是關於當n很大時哪些算法是高效或可行的關鍵。
在列舉的例子中，所有Big-O符號表明，在*某點* A1增長得比A2快，使得A2成爲更好的選擇。它沒有告訴你什麼時候這一點。當你不考慮這種比較成爲一個問題時。有幾個算法的異常大O，但隱藏的常量是如此之高，使算法在實踐中不切實際，除了最可笑的大問題。 – Nuclearman 2014-09-22 08:24:50
在第一個引號句子的「*比較*」之前插入「* general *」或「* sweeping *」可能會有幫助。 – dimo414 2016-05-10 04:39:30