是大O（logn）日志基础？

2018-05-31 09:15:39

对于二进制搜索树类型的数据结构，我看到Big 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（）表示法之前，差异非常重要。当推导出通过big-O表示法传送的多项式时，在应用O（） - 表示法之前，使用log2 N以外的对数对此示例是不正确的。只要多项式用于通过big-O（）表示法传递最坏情况的运行时，那么使用什么对数就没有关系。

大O符号不受对数碱基的影响，因为不同碱基中的所有对数都与常数因子相关， O(ln n)等于O(log n) 。

它的基础是什么并不重要，因为大O符号通常写成只显示n的渐近最高阶，所以常数系数将会下降。由于不同的对数基数相当于一个常数系数，因此这是多余的。

也就是说，我可能会假定日志基数为2。

链接地址: http://www.djcxy.com/p/6805.html