algorithm - 您可以使用Big O表示法进行加法/乘法吗？

我现在在上一个算法课，我们要学习大O符号之类的。上次，我们讨论了

O (n^2 + 3n + 5) = O(n^2)

我想知道，同样的规则是否适用于此：

O(n^2) + O(3n) + O(5) = O(n^2)

另外，下列符号是否有效？

O(n^2) + n

或

O(n^2) + Θ (3n+5)

后面的n在o之外，所以我不确定它应该是什么意思。在第二个符号中，我加上O和Θ。

最佳答案

至少出于实际目的，the Landau O(...) can be viewed as a function（因此对其符号提出上诉）This function has properties for standard operations，例如：

O(f(x)) + O(g(x)) = O(f(x) + g(x))
O(f(x)) * O(g(x)) = O(f(x) * g(x))
O(k*f(x)) = O(f(x))

对于定义良好的函数f(x)和g(x)，以及一些常数k。
因此，举你的例子，
是：O(n^2) + O(3n) + O(5) = O(n^2)
以及：
O(n^2) + n = O(n^2) + O(n) = O(n^2)，
O(n^2) + Θ(3n+5) = O(n^2) + O(3n+5) = O(n^2)

关于algorithm - 您可以使用Big O表示法进行加法/乘法吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57830311/