这源于编写程序以找到具有大小m和n分别具有时间复杂度的两个排序数组的中值O(log(m + n)).
我可以找出解决方案O(log(m) + log(n)).它符合上述时间要求吗？
我认为这是积极的,因为:
log(m) + log(n) = log(m*n) <= log((m+n)^2) = 2*log(m+n) = O(log(m+n))
换句话说,存在k = 2和m0 = n0 = 1.对于任何m > m0 and n > n0,有log(m*n) <= k*log(m + n).
是否存在缺陷,或者我是否正确？
更一般地说,给定常数a,我们可以log(n^a) = O(log(n))用相同的推理说出来吗？
感谢大卫的回答.维基百科上的Big-O表示法也提到了这一点:
"We may ignore any powers of n inside of the logarithms. The set O(log n) is exactly the same as O(log(n^c))."