O(n*log n) + O(m*log m) 与 O((n+m)log(n+m))

Question

哪种复杂度更好O(n*log n) + O(m*log m) vs O((n+m)log(n+m)) where n>1 and m>1。 谁也可以给出数学证明？

Answer 1

以下是我认为它们同样出色的原因：

情况A：m和n增长速度一样快：

O(n*log n) + O(m*log m) = 2*O(n*log n) = O(n*log n)   // positive constant removed
O((n+m)log(n+m)) = O((2n)log(2n)) = O((n)log(n))      // positive constants removed

案例 B：m 或 n 的增长速度比另一个快（假设 n，w.l.o.g。）

O(n*log n) + O(m*log m) = O(n*log n)    // slower growing part removed
O((n+m)log(n+m)) = O(n*log n)           // slower growing part removed