对于算法而言,对数的基础是什么?

sab*_*mim 8 big-o

在考虑O(log(N))的时间复杂度时,日志的基础是什么?

GMa*_*ckG 15

所有对数都通过一些常数相关联.(因此改变基础公式).因为我们通常忽略复杂性分析中的常数,所以基数并不重要.

通常,在推导算法时,基数被认为是2.考虑类似合并排序的那种.您可以从中构造一个,并且树的高度为log? n,因为每个节点都有两个分支.


Rob*_*ker 10

无关紧要,无论使用何种基础,相对复杂性都是相同的.

  • @Andres Shepherd:要扩展对注释的其他响应,log_a(n)/ log_b(n)是一个常量,对于n的所有值都是相同的.另一方面,当n增长时,(n ^ 2)/(n ^ 3)的比率增加.算法复杂性分析关注资源需求随着n的增加而增加,因此常数无关紧要.随n变化的值. (3认同)