大O（logn）日志是e吗？

Question

对于二进制搜索树类型的数据结构，我看到Big O标记通常记为O（logn）。如果日志中的字母为小写“ l”，这是否意味着以自然对数描述的对数e（n）为对数？很抱歉这个简单的问题，但是我一直很难区分不同的隐式对数。

Answer 1

一旦用big-O（）表示法，两者都是正确的。但是，在推导 O（）多项式的过程中，对于二进制搜索，只有log 2是正确的。我认为这种区别是您提出问题的直观灵感。另外，以我的观点，写O（log 2 N）对于您的示例更好，因为它可以更好地传达算法运行时间的推导。在big-O（）表示法中，常数因子被删除。从一个对数底数转换为另一对数底数需要乘以一个常数因子。因此，由于常数因子，O（log N）等于O（log 2 N）。但是，如果您可以轻松地在答案中输入log 2 N，则这样做更具教学意义。在二叉树搜索的情况下，你是正确的，日志2 N为大O（）运行时的推导过程中引入。在将结果表示为big-O（）表示法之前，区别非常重要。当推导要通过big-O表示法传递的多项式时，在此示例中，在应用O（）表示法之前使用log 2 N 以外的对数是不正确的。一旦使用了多项式通过big-O（）表示法来传达最坏情况的运行时，使用什么对数就无关紧要了。

Answer 2

Big O表示法不受对数底数的影响，因为不同底数中的所有对数均与一个常数因子相关，O(ln n)等效于O(log n)。