关于时间复杂度，大O符号

Question

假设n1,n2 > k。

 O(k(n1+n2-k)) = O(k(max(n1,n2)) ?

还有

 O(n1+n2) = O(max(n1,n2)) ?

谢谢

Answer 1

Is the claim O(k(n1+n2-k)) = O(k(max(n1,n2)) true?

我们知道 k < min{n1,n2} - 因此：

k(n1+n2-k) = k(max{n1,n2} + min{n1,n2} -k) > k(max{n1,n2})

所以，证明 O(k(max(n1,n2)) 是 O(k(n1+n2-k))

的子集是很简单的

我们还需要反过来展示，这也很容易，因为 2k*max{n1,n2} 在 O(k(max(n1,n2)) 中，而

k(n1+n2-k) < k(max{n1,n2} + max{n1,n2}) -k) < 
           < k(max{n1,n2} + max{n1,n2}))
           = 2 k*max{n1,n2}

所以，这个说法是正确的。

Does O(n1+n2) = O(max(n1,n2)) ?

这是正确的。由于max{n1,n2} <= n1+n2 <= 2*max{n1,n2}，我们在分析大O符号时不关心常量。

Regarding time complexity, big O notation