问题描述
对于二进制搜索树类型的数据结构，我看到Big O表示法通常记为O(logn).在日志中使用小写字母"l"，这是否意味着以自然对数描述的对数e(n)为对数?很抱歉这个简单的问题，但是我一直很难区分不同的隐式对数.
For binary search tree type of data structures, I see the Big O notation is typically noted as O(logn). With a lowercase 'l' in log, does this imply log base e (n) as described by the natural logarithm? Sorry for the simple question but I've always had trouble distinguishing between the different implied logarithms.
推荐答案
一旦以big-O()表示法表示，两者都是正确的.但是，在O()多项式的推导期间，对于 binary 搜索，只有log 是正确的.我认为这种区别是您提出问题的直观灵感.
Once expressed in big-O() notation, both are correct. However, during the derivation of the O() polynomial, in the case of binary search, only log is correct. I assume this distinction was the intuitive inspiration for your question to begin with.
据我所知，为您的示例编写O(log N)更好，因为它可以更好地传达算法运行时间的推论.
Also, as a matter of my opinion, writing O(log N) is better for your example, because it better communicates the derivation of the algorithm's run-time.
在big-O()表示法中，常数因子被删除.从一个对数底数转换为另一对数底数需要乘以一个常数因子.
In big-O() notation, constant factors are removed. Converting from one logarithm base to another involves multiplying by a constant factor.
由于常数因子，所以O(log N)等于O(log N).
So O(log N) is equivalent to O(log N) due to a constant factor.
但是，如果您可以轻松地在答案中输入log N，则这样做更具教学意义.在二叉树搜索的情况下，正确的是在导出big-O()运行时期间引入了log N.
However, if you can easily typeset log N in your answer, doing so is more pedagogical. In the case of binary tree searching, you are correct that log N is introduced during the derivation of the big-O() runtime.
在将结果表示为big-O()表示法之前，区别非常重要.当推导要通过big-O表示法传递的多项式时，在此示例中，在应用O()表示法之前，使用log N以外的对数是不正确的.一旦多项式用于通过big-O()表示法传递最坏情况的运行时，使用什么对数就无关紧要.
Before expressing the result as big-O() notation, the difference is very important. When deriving the polynomial to be communicated via big-O notation, it would be incorrect for this example to use a logarithm other than log N, prior to applying the O()-notation. As soon as the polynomial is used to communicate a worst-case runtime via big-O() notation, it doesn't matter what logarithm is used.
这篇关于大O(logn)日志是e吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！