是大 O(logn) 对数基数 e 吗? [英] Is Big O(logn) log base e?

问题描述

对于二叉搜索树类型的数据结构，我看到大 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()多项式的推导过程中，在二分搜索的情况下，只有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() 符号之前，差异非常重要.在推导要通过大 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 吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！