大O(logn)日志基数是多少？

Question

对于二进制搜索树类型的数据结构,我看到Big O表示法通常标记为O(logn).在日志中使用小写的"l",这是否意味着日志基数e(n)如自然对数所描述的那样？抱歉这个简单的问题,但我总是无法区分不同的隐含对数.

Answer 1

大O表示法不受对数基数的影响,因为不同基数中的所有对数都是由常数因子相关的,O(ln n)相当于O(log n).

但是*为什么*你在谈论这个问题,当它与这个问题没有关系而只是混淆了？ (4认同)
hobbs:因为这个事实是OP受到鼓舞的原因.我试图将他的想法与答案联系起来,所以他理解为什么他有他的直觉,为什么它不适用于O(),而不是过度应用他在这里学到的东西到分析的推导部分.没有解决误解根本原因的简洁答案可能会导致进一步的误解.这是糟糕的教学法. (4认同)
@Heath Hunnicutt:如果你正在进行渐近分析,那没关系.你等到最后一分钟扔掉一些大的O并没有改变这样一个事实,即我可以将所有对数乘以一些愚蠢的常数并在所有步骤中改变基数.也就是说,如果我有一些涉及`log_2 n`的分析,我可以进入并用`log_pi 2*log_2 n/log_pi 2`替换`log_2 n`,然后最后得到一个具有`log_pi的分析到处都是2*log_pi n`.现在我的分析就是`log_pi n`. (4认同)
图形很整洁,但想想O() - 多项式的推导......在应用O()之前,只有log-base-2对二进制搜索是正确的. (2认同)
@Heath Hunnicutt:但重点是无所谓. (2认同)

Answer 2

一旦用big-O()表示法表示,两者都是正确的.但是,在推导 O()多项式期间,在二分搜索的情况下,只有log ₂是正确的.我认为这种区别是你问题的直觉灵感.

另外,作为我的观点,编写O(log ₂ N)对于您的示例更好,因为它更好地传达了算法运行时的推导.

在big-O()表示法中,常数因子被删除.从一个对数基数转换为另一个对数基数涉及乘以常数因子.

因此,由于常数因子,O(log N)等于O(log ₂ N).

但是,如果您可以在答案中轻松排版log ₂ N,那么这样做更具教学意义.在二叉树搜索的情况下,在big-O()运行时的派生期间引入log ₂ N是正确的.

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

"在推导O()多项式期间,在二进制搜索的情况下,只有log2是正确的." -1表示数学不佳.x(n)~O(f(n))的定义表明存在常数c,使得所有n> n_0的c*(f(n))<x(n).因此,在分析期间,常数系数完全不相关. (11认同)
但是很容易证明`log_2 n`在任何基数'a`的'Θ(log_a n)`中,所以我不确定我是否看到使用base 2是"更正确". (4认同)
由于log2(x)等于log10(x)/ log10(2),因此您可以以任一方式导出它.日志在任何时候都不是严格的基数2. (3认同)
好吧,我添加了清晰度,但我确信你觉得我的回答可能会让人感到困惑.实际上,这里的大部分答案都没有考虑到OP的直觉,并试图教他很多.我并没有被竞争对手所震撼,我对教育学的低调感到很难过. (2认同)

Answer 3

它的基数并不重要,因为big-O表示法通常只显示渐近最高阶n,因此常数系数会消失.由于不同的对数基数等于常系数,因此它是多余的.

也就是说,我可能会假设log base 2.

Answer 4

两者都是正确的。想想这个

log2(n)=log(n)/log(2)=O(log(n))
log10(n)=log(n)/log(10)=O(log(n))
logE(n)=log(n)/log(E)=O(log(n))