math - Big O(logn) 对数底数是 e 吗？

Question

对于二叉搜索树类型的数据结构，我看到 Big O 表示法通常记为 O(logn)。 log 中的小写“l”是否意味着自然对数所描述的以 e (n) 为底的对数？很抱歉问这个简单的问题，但我总是很难区分不同的隐含对数。

Answer 1

一旦用 big-O() 表示法表示，两者都是正确的。然而，在 O() 多项式的推导过程中，在二元搜索的情况下，只有 log₂ 是正确的。我认为这种区别是您提出问题的直观灵感。

此外，我认为，编写 O(log₂ N) 更适合您的示例，因为它可以更好地传达算法运行时的推导。

在 big-O() 表示法中，常数因子被删除。从一种对数基数转换为另一种对数基数需要乘以一个常数因子。

因此，由于常数因子，O(log N) 相当于 O(log₂ N)。

但是，如果您可以轻松地在答案中排版 log₂ N，则这样做更具教学意义。在二叉树搜索的情况下，您是正确的，在 big-O() 运行时的推导过程中引入了 log₂ N 。

在将结果表示为 big-O() 表示法之前，差异非常重要。当导出要通过大 O 表示法传递的多项式时，在应用 O() 表示法之前，使用除 log₂ N 之外的对数对本例来说是不正确的。一旦使用多项式通过 big-O() 表示法传达最坏情况运行时间，使用什么对数就不再重要了。