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