O(log(A)) + O(log(B)) = O(log(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]，你是对的。

if m = O(n) then O(n + m) = O(2n) = 2 O(n) = O(n) (2 is a constant)

Answer 2

这总是正确的：O(X + Y) = O(X) + O(Y)

此外，复杂性也没有代数那么宝贵。这意味着，如果某些东西在代数上是相等的，那么它在复杂度上一定是相等的。(当然，如果某些东西在复杂度上是相等的，那么它在代数上就不必相等)

Answer 3

1是真的。这就是证明，让c_1和c_2是你通过定义一个函数的大O得到的常数。因此，您需要：

O(log(A)) + O(log(B))  
= c_1*log(A) + c_2*log(B)
<= c*log(A) + c*log(B)  where c=max{c_1,c_2}
= c*(log(A)+log(B))
= O(log(A*B))

用同样的逻辑，你可以看到3是正确的，所以你有：

   O(log(A)) + O(log(B)) 
    = c_1*log(A) + c_2*log(B) [5]

因此，假设log(A)是log(A)和log(B)的最大值，您可以得到前面的等式5是：

    <= c_1*log(A) + c_2*log(A)
    = (c_1+c2)*log(A)
    = O(log(A)) 
    = O(max(log(A), log(B)))

它可以简化为：

    = max(O(log(A)), O(log(B)) )