algorithm - 大O符号计算，O(n) * O(log n) = O(n log n)

Question

我需要设计一种算法，能够用给定的 O 表示法进行一些计算。自从我上次使用 O 符号计算以来已经有一段时间了，我对如何将不同的 O 符号加在一起感到有点困惑。

O(n) * O(log n) = O(n log n)

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

O(n) * O(log n) + O(n log n) = O(n log n) + O(n log n) = O(n log n)

这些正确吗？我还忽略了哪些其他规则？

Answer 1

rule乘法非常简单:

O(f) * O(g) = O(f * g)

如果您希望它适用于任意函数，则两个 O 项的总和更难计算。
但是，如果 f ∈ O(g)，则 f + g ∈ O(g)。

因此，您的计算是正确的，但您的原始标题不正确；

O(n) + O(log n) = O(n)