大 O 代数简化

Question

简化一个大 O 表达式

1. 我们省略了所有常量
2. 我们忽略了 n 的低次幂

例如：

O(n + 5) = O(n)

O(n² + 6n + 7) = O(n²)

O(6n1/3 + n1/2 + 7) = O(n1/2)

我在这些例子中是对的吗？

Answer 1

你几乎是对的。第二条规则应该是，除了具有最大极限的项（趋向n无穷大）之外，您忽略所有项。如果您的项不是 的幂n（例如logs 或其他数学函数），这一点很重要。

还值得注意的是，大 O 符号有时会掩盖其他重要的细节。的算法O(n log n)将比 的算法具有更好的性能O(n^2)，但前提是输入足够大，使得大多数项能够主导运行时间。对于您在特定应用程序中实际必须处理的大小输入，O(n^2)算法实际上可能表现更好！