Big O表示法Log Base 2或Log Base 10

Question

当文章/问题表明算法的Big O运行时间是O(LogN)时.

例如,Quicksort的运行时间为O(LogN),其中它是Log base 10,但二叉树的高度为O(LogN + 1),其中它是Log base 2

题

1)我感到困惑的是它是Log base 10还是Log base 2,因为不同的文章使用不同的对数作为对数.

2)如果它的Log base 2或Log base 10 ??它会有所不同吗？

3)当我们看到O(LogN)时,我们可以假设它是指Log base 10吗？

Answer 1

我认为日志的基础无关紧要,因为相对复杂性是相同的,无论使用何种基础.

所以你可以把它想象为O(log ₂ X)= O(log ₁₀ X)

还要提到的是,对数与某些常数相关.

所以

log 10(x)= log 2(x)/ log 2(10)

所以大多数时候我们通常忽略复杂性分析中的常数,因此我们说基数并不重要.

此外,您可能会发现大多数时候基数被认为是2,如合并排序.树的高度为log? n,因为节点有两个分支.

1)我感到困惑的是它是Log base 10还是Log base 2,因为不同的文章使用不同的对数作为对数.

因此,如上所述,这种基础的变化并不重要.

2)如果它的Log base 2或Log base 10 ??它会有所不同吗？

不,没关系.

3)当我们看到O(LogN)时,我们可以假设它是指Log base 10吗？

是的,如果你知道基本转换规则,你可以假设.

Answer 2

对于所有x, log 10 (x)= log 2(x)/ log 2(10).1/log 2(10)是常数乘数,可以从渐近分析中省略.

更一般地,任何对数的底数可以从改变一个到b(二者恒定WRT Ñ通过logₐ分割)(b),所以可以日志碱基之间的大于一个可自由切换:O(log₁₀(Ñ))是与O(log 2(n)),O(ln(n))等相同.

这样做的一个例子是B树不能渐近地击败平衡二叉搜索树,即使它们在分析中给出更高的对数基数.只是有更好的常数.

Answer 3

在Big O表示法中,O(log(n))所有基础都是相同的.这是由于对数基数转换:

log2(n) = log10(n)/log10(2)

1/log10(2)只是一个常数乘数因子,因此O(log2(n))也是如此O(log10(n))