algorithm - 为什么我们不能使用 O-Notation 来比较算法？

Question

来 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 慢。

Answer 1

增长慢并不意味着绝对快。

你有没有这样的经历，你的 friend 在你年轻的时候比你高，但你最终成为你们两个之间更高的人，或者相反？

意思是一样的。 A1 可能更适合、更快速地解决小规模问题。遇到大问题只会变慢。

如果您想了解更多关于数学背景的细节，那么强烈推荐 Robert Sedgewick 的“算法分析导论”。