大 O 表示法 log(n^2) = O(log(n))

Question

嗨，我想知道 log(n^2) 是否可以写成 O(log(n)) ？

我很困惑，因为 n^2 不是 O(n) 但在这种情况下，因为它受 log 限制，我们可以这么说吗？

Answer 1

对数的基本数学属性： log(n^2) = 2*log(n)其中^表示“的幂”。

所以O(log(n^2)) = O(2*log(n))。

对于复杂性计算，重点是极限内的收敛行为，因此常数乘数被取消。这意味着O(2*log(n)) = O(log(n))。

将以上所有内容放在一起，结果是O(log(n^2)) = O(log(n))。