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

Question

对于二叉搜索树类型的数据结构，我看到大 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() 表示法传达最坏情况的运行时间，使用什么对数就无关紧要了。