分析时间复杂度时，对数基数 2 等于对数基数 3？

Question

Intro 练习 4.4.6 的大多数解决方案。对算法第 3 版说，n*log3(n) = (n*lg(n)) 的大欧米茄。

当我们讨论算法的时间复杂度时，这是否意味着 log3(n) 等价于 log2(n)？

谢谢

Answer 1

就 big-Oh 表示法而言，对数的底数没有任何实际区别，因为这个重要的属性称为Change of Base。

根据这个性质，改变对数的底数，就大欧记法而言，只会通过一个常数因子影响复杂度。

所以，是的。在 big-Oh 符号方面，log3(n) 等价于 log2(n)。