对于二叉搜索树类型的数据结构，我看到大 O 表示法通常记为 O(logn)。对数中的小写“l”是否意味着自然对数所描述的以 e (n) 为底的对数？对不起，这个简单的问题，但我总是无法区分不同的隐含对数。
最佳答案
一旦用 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() 表示法传达最坏情况的运行时，使用什么对数就无关紧要。
关于math - 是大 O(logn) 对数基数 e 吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1569702/