你能用Big O符号做加法/乘法吗？

Question

我目前正在进行算法课程,我们正在介绍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和Θ.

Answer 1

至少出于实际目的,Landau O(...)可以被视为一种功能(因此其符号的吸引力). 此函数具有标准操作的属性,例如:

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)