algorithm - 具有两个变量的大 O 表示法

Question

这源于编写一个程序到find the median of two sorted arrays尺寸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 notation也提到了这一点在维基百科上:

"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))."

Answer 1

是的，您在所有方面都是正确的。 Log 增长足够慢，渐近类对内部函数不是很敏感。