big-o - 如何证明渐近符号的组合？

Question

我想我很好地掌握了 Big O、omega 和 theta 符号的含义以及如何证明函数是否是其中之一。我不明白如何证明它们的组合，就像在问题中一样。有人可以向我解释一下吗？

Θ(n) + O(n^3) = O(n^3)

编辑：错字，原来说不等于

Answer 1

实际上，我认为 Θ(n) + O(n^3) = O(n^3)。

如果你有一个函数 f 具有常数 k1 和 k2 使得 k1*n <= f(n) <= k2*n 渐近（这是 Θ），并且你有一个函数 g 具有常数 k3 使得 g(n) < = k3*n^3 渐近（即左边的 big-O），那么有一个常数 k4 使得 f(n) + g(n) <= k4*n^3 渐近（右边的 big-O）。只需将 k4 = k2 + k3 限制为 n >= 1，因为如果 n >= 1 则 k2*n + k3*n^3 <= k2*n^3 + k3*n^3 = (k2 + k3 )*n^3 = k4*n^3。

要显示像您要求的那样的不等式更简单：那么您只需要展示满足左侧边界但 f(n) + g(n) 不满足边界的特定f 和 g右手边。