Big O(logn) 对数底数是 e 吗？
对于二叉搜索树类型的数据结构，我看到 Big O 表示法通常记为 O(logn)。 log 中的小写“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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
一旦用 big-O() 表示法表示，两者都是正确的。然而，在 O() 多项式的推导过程中，在二元搜索的情况下，只有 log2 是正确的。我认为这种区别是您提出问题的直观灵感。
另外，我认为，编写 O(log2 N) 更适合您的示例，因为它可以更好地传达算法运行时的推导。
在 big-O() 表示法中，常数因子被删除。从一种对数基数转换为另一种对数基数需要乘以一个常数因子。
因此，由于常数因子，O(log N) 相当于 O(log2 N)。
但是，如果您可以轻松地在答案中排版 log2 N，那么这样做更具教学意义。在二叉树搜索的情况下，您是正确的，在 big-O() 运行时的推导过程中引入了 log2 N 。
在将结果表示为 big-O() 表示法之前，差异非常重要。当导出要通过大 O 表示法传递的多项式时，在应用 O() 表示法之前，使用 log2 N 以外的对数对本例来说是不正确的。一旦使用多项式通过 big-O() 表示法来传达最坏情况的运行时间，使用什么对数就不再重要了。
Once expressed in big-O() notation, both are correct. However, during the derivation of the O() polynomial, in the case of binary search, only log2 is correct. I assume this distinction was the intuitive inspiration for your question to begin with.
Also, as a matter of my opinion, writing O(log2 N) is better for your example, because it better communicates the derivation of the algorithm's run-time.
In big-O() notation, constant factors are removed. Converting from one logarithm base to another involves multiplying by a constant factor.
So O(log N) is equivalent to O(log2 N) due to a constant factor.
However, if you can easily typeset log2 N in your answer, doing so is more pedagogical. In the case of binary tree searching, you are correct that log2 N is introduced during the derivation of the big-O() runtime.
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 log2 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 表示法不受对数底数的影响，因为不同底数的所有对数都通过常数相关因子，
O(ln n)相当于O(log n)。Big O notation is not affected by logarithmic base, because all logarithms in different bases are related by a constant factor,
O(ln n)is equivalent toO(log n).两者都是正确的。想想这个
Both are correct. Think about this
它的基数是什么并不重要，因为大 O 表示法通常只显示
n的渐近最高阶，因此常数系数将会消失。由于不同的对数底相当于常数系数，因此是多余的。也就是说，我可能会假设对数以 2 为底。
It doesn't really matter what base it is, since big-O notation is usually written showing only the asymptotically highest order of
n, so constant coefficients will drop away. Since a different logarithm base is equivalent to a constant coefficient, it is superfluous.That said, I would probably assume log base 2.
是的，当谈论大 O 表示法时，基数并不重要。然而，从计算角度来说，当面对真正的搜索问题时，它确实很重要。
当培养对树结构的直觉时，了解二叉搜索树可以在 O(n log n) 时间内搜索是有帮助的，因为这是树的高度 - 也就是说，在具有 n 个节点的二叉树中，树深度为 O(n log n)（以 2 为底）。如果每个节点有三个子节点，则仍然可以在 O(n log n) 时间内搜索树，但使用以 3 为底的对数。从计算角度来看，每个节点的子节点数量会对性能产生很大影响（例如：链接文本）
享受吧！
保罗
Yes, when talking about big-O notation, the base does not matter. However, computationally when faced with a real search problem it does matter.
When developing an intuition about tree structures, it's helpful to understand that a binary search tree can be searched in O(n log n) time because that is the height of the tree - that is, in a binary tree with n nodes, the tree depth is O(n log n) (base 2). If each node has three children, the tree can still be searched in O(n log n) time, but with a base 3 logarithm. Computationally, the number of children each node has can have a big impact on performance (see for example: link text)
Enjoy!
Paul
首先，您必须了解函数 f(n) 的复杂度为 O( g(n) ) 意味着什么。
正式定义为： *函数 f(n) 被称为 O(g(n)) iff |f(n)| <= C * |g(n)|每当 n > 时k，其中 C 和 k 是常数。*
因此令 f(n) = n 的对数底 a，其中 a > 1 且 g(n) = n 的以 b 为底的对数，其中 b > 1
注意： 这意味着值 a 和 b 可以是任何大于 1 的值，例如 a=100 且 b = 3
现在我们得到以下结果： log base a n 被称为 O(n 的 log base b) iff |log base a of n| <= C * |n 的以 b 为底的对数|每当 n > 时k
选择 k=0，C= b 的以 a 为底的对数。
现在我们的等式如下所示： |log以a为底的n| <= b 的以 a 为底的对数 * |n 的以 b 为底的对数|每当 n > 时0
注意右边，我们可以操纵方程： = log base a of b * |log base b of n| = |n 的以 b 为底的对数 | * b 的对数底 a = |b 的对数底 a^(n 的对数 b 底)| = |以a为底的n的对数|
现在我们的等式如下所示： |log以a为底的n| <= |n 的以 a 为底的对数|每当 n > 时0
无论 n、b 或 a 的值是什么，方程始终为真，除了它们的限制 a、b>1 和 n>0 之外。
所以 n 的对数底 a 是 O(n 的对数底 b) 并且由于 a,b 并不重要，我们可以简单地省略它们。
您可以在此处观看 YouTube 视频：https://www.youtube.com/ watch?v=MY-VCrQCaVw
您可以在这里阅读相关文章：https://medium.com/@randerson112358/omitting-bases-in-logs-in-big-o-a619a46740ca
First you must understand what it means for a function f(n) to be O( g(n) ).
The formal definition is: *A function f(n) is said to be O(g(n)) iff |f(n)| <= C * |g(n)| whenever n > k, where C and k are constants.*
so let f(n) = log base a of n, where a > 1 and g(n) = log base b of n, where b > 1
NOTE: This means the values a and b could be any value greater than 1, for example a=100 and b = 3
Now we get the following: log base a of n is said to be O(log base b of n) iff |log base a of n| <= C * |log base b of n| whenever n > k
Choose k=0, and C= log base a of b.
Now our equation looks like the following: |log base a of n| <= log base a of b * |log base b of n| whenever n > 0
Notice the right hand side, we can manipulate the equation: = log base a of b * |log base b of n| = |log base b of n| * log base a of b = |log base a of b^(log base b of n)| = |log base a of n|
Now our equation looks like the following: |log base a of n| <= |log base a of n| whenever n > 0
The equation is always true no matter what the values n,b, or a are, other than their restrictions a,b>1 and n>0.
So log base a of n is O(log base b of n) and since a,b doesn't matter we can simply omit them.
You can see a YouTube video on it here: https://www.youtube.com/watch?v=MY-VCrQCaVw
You can read an article on it here: https://medium.com/@randerson112358/omitting-bases-in-logs-in-big-o-a619a46740ca
从技术上讲，基数并不重要，但您通常可以将其视为基数 2。
Technically the base doesn't matter, but you can generally think of it as base-2.