问当分析时间复杂性时，日志基2等于日志基3？
EN

Stack Overflow用户

提问于 2014-05-25 21:58:10

回答 1查看 6.6K关注 0票数 6

大多数解决方案的练习4.4.6介绍。对于算法第3版，n*lg 3(N)= (n*lg(n))的大omega。

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

谢谢

回答已采纳

发布于 2014-05-25 22:03:26

就大-欧表示法而言，由于这的重要性质(称为Change of Base )，对数的基数没有任何真正的区别。

根据这一性质，改变对数的基数，在大-哦表示法，只会影响一个常数的复杂性。

所以，是的。在大-Oh表示法中，log3(n)等价于log2(n).

票数 8

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/23860356

复制

相似问题

问当分析时间复杂性时，日志基2等于日志基3？EN