你能用大 O 符号做 addition/multiplication 吗？

Question

我目前正在学习一种算法 class，我们正在介绍大 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

表示法：

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

以及，例如：

f(n,m) = n^2 + m^3 + O(n+m)

滥用相等符号，因为它违反了相等公理。为了更正式地正确，您需要将 O(g(x)) 定义为集值函数，其值是所有增长速度不快于 g(x) 的函数，并使用集成员表示法来表示特定函数是集合的成员。

朗道符号 (Big O) 没有定义加法和乘法。

Answer 2

以下符号也成立

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

和

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

希望它有意义...

Answer 3

在复杂性理论中，Landau 符号用于函数集。因此O(*)不代表一个函数而是一个集合。 + 运算符没有为集合定义，但是，在分析函数时通常使用以下运算符：

O(*) + g(n)

这通常表示一组函数，其中 g(n) 添加到 O(*) 中的每个函数。结果集可以再次用大 O 表示法表示。

O(*) + O(**)

这个类似。但是，它的行为类似于一种笛卡尔积。 O(**) 中的每个函数都添加到 O(*) 中的每个函数。

O(*) + Θ(*)

此处适用相同的规则。但是，由于O(*)的松动，结果通常不能表示为Θ(**)。表示成O(**)还是可以的

Answer 4

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)

Can you do addition/multiplication with Big O notations?