大 O 代数简化

Question

为了简化大 O 表达式，我们遵循以下规则：

1.省略所有常量；

2.忽略 n 的低次幂。

例如：

O(n + 5) = O(n)

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

O(6n^1/3 + n^1/2 + 7) = O(n^1/2)

这些例子的翻译是正确的吗？

- Michael harris

Answer 1

1. 我们省略所有常数

严格来说，您不会省略所有常数，只是最外层的乘法常数。这意味着O(cf(n)) = O(f(n))。加法常数也可以，因为从某个n开始，f(n) < f(n)+c < 2f(n)，所以O(f(n)+c) = O(f(n))。

但是您不能省略复合函数内部的常数。有时可能会这样做（例如O(log(cn))甚至是O(log(n^c))），但并不普遍适用。例如考虑2^2n，可能会诱惑您省略2并将其放入O(2^n)，但这是错误的。

2. 我们忽略较低幂次的n

这是正确的，但请记住，您并不总是使用多项式函数。您通常可以忽略添加的渐近较低函数。假设您有f(n)和g(n)，当g(n) = O(f(n))时，则O(f(n) + g(n)) = O(f(n))。

您不能在乘法中这样做。

- pepo

Answer 2

你的观点基本正确。第二个规则应该是，当 n 趋近于无穷大时，只需考虑具有最大极限的项，而忽略其余项。如果你有一些不是 n 的幂次方的项，比如 log 或其他数学函数，这一点就显得尤为重要。

另外值得注意的是，大 O 表示法有时会掩盖重要的其他细节。一个 O(n log n) 的算法性能将优于一个 O(n^2) 的算法，但前提是输入的大小足够大，以至于那些主要的项支配运行时间。也许对于你在特定应用中实际处理的输入大小，O(n^2) 算法的性能实际上更好！

- Blckknght