大O符号对数基数2或对数基数10
大O符号对数基数2或对数基数10
提问于 2013-12-21 01:50:14
当文章/问题表明算法的大O运行时间是O(LogN)时。
例如，快速排序的大O运行时间为O (LogN)，其中它是对数底10，但二叉树的高度是O(LogN+1)，其中它是对数底2
问题
1)我搞不清是对数底10还是对数底2，因为不同的文章使用不同的底作为对数。
2)对数基是2还是对数基10有区别吗？？
3)当我们看到O(LogN)时，我们能假设它是以10为底的对数吗？
回答 2
Stack Overflow用户
发布于 2013-12-21 01:53:49
对数₁₀( x )=所有x的对数₂(X)/对数₂(10)。1/对数₂(10)是常数乘数，可以从渐近分析中省略。
更普遍的是，任何对数的底都可以从a改为b(两者都是常量wrt。n)通过除以对数ₐ(B)，从而可以在大于1的对数底之间自由切换:O(对数₁₀(N))与O(对数₂(N))、O(ln(n))等。
这样做的一个示例结果是，B-trees不会渐进地击败平衡二进制搜索树，即使它们在分析中提供了更高的对数基数。只是有更好的常量。
Stack Overflow用户
发布于 2013-12-21 01:57:15
在大O表示法中，O(log(n))对于所有的基都是相同的。这是由于以对数为底的转换：
log2(n) = log10(n)/log10(2)1/log10(2)只是一个恒定的乘数因子，因此O(log2(n))与O(log10(n))相同
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20709267
复制相关文章
相似问题