big-o - O(日志(A))+ O(日志(B))= O(日志(A * B))？

Question

这是真的:

log(A) + log(B) = log(A * B)    [0]

这也是真的吗？

O(log(A)) + O(log(B)) = O(log(A * B)) [1]

据我了解

O(f(n)) + O(g(n)) = max( O(f(n)), O(g(n)) ) [2]

或者换句话说——如果一个函数比另一个函数渐近增长得更快，那么只有那个函数与大 O 符号相关。那么也许这个等式是正确的？

O(log(A)) + O(log(B)) = max( O(log(A), O(log(B)) ) [3]

Answer 1

O 是线性的。

因此 O(a) + O(b) = O(a + b)。

所以 O(log(A)) + O(log(B)) = O(log(A) + log(B)) = O(log(A * B))

---

关于[3]，你是对的。

如果 m = O(n) 则 O(n + m) = O(2n) = 2 O(n) = O(n)(2 是常数)