来 self 的教科书:
O-notation and Complexity of Algorithms
It is important not to try and make comparisons between algorithms using O-notation.
For example, suppose algorithm A1 and A2 both solve the same problem, A1 has complexity O(n^3) and A2 has complexity O(n^2).
The above statements are perfectly reasonable.
Observe that we cannot conclude that A2 is more efficient than A1 in this situation!
为什么不呢？ A2 的复杂度增长比 A1 慢。
最佳答案
增长慢并不意味着绝对快。
你有没有这样的经历，你的 friend 在你年轻的时候比你高，但你最终成为你们两个之间更高的人，或者相反？
意思是一样的。 A1 可能更适合、更快速地解决小规模问题。遇到大问题只会变慢。
如果您想了解更多关于数学背景的细节，那么强烈推荐 Robert Sedgewick 的“算法分析导论”。
关于algorithm - 为什么我们不能使用 O-Notation 来比较算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25964719/