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

小编典典

algorithm

我目前正在上算法课，我们将介绍Big 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和Θ。

阅读 377

2020-07-28

共1个答案

小编典典

至少出于实际目的，可以将 LandauO(...)视为一种功能（因此具有其符号的吸引力）。
此函数具有标准操作的属性，例如：

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)

2020-07-28