big-o - 就算法而言，对数的底是什么？

Question

在考虑 O(log(N)) 的时间复杂度时，log 的基础是什么？

score 15 · Accepted Answer

所有对数都与某个常数相关。（因此改变基数公式）。因为我们通常在复杂性分析中忽略常数，所以基数无关紧要。

通常，在推导算法时，基数被认为是 2。考虑一种类似合并排序的排序。你可以用它构造一棵树，树的高度为log₂ n，因为每个节点都有两个分支。

score 10 · Accepted Answer

10

没关系，无论使用何种基础，相对复杂性都是相同的。

于 2009-11-11T04:52:29.427 回答

score 2 · Accepted Answer

2

一种思考方式是 O(log ₂ X) = O(log ₁₀ X) = O(log _N X)

于 2009-11-16T13:17:10.563 回答

3 回答 3