Big-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

该规则乘法是非常简单的:

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

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

因此,您的计算是正确的,但您的原始标题不是;

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