大O(logn)日志是e吗? [英] Is Big O(logn) log base e?

查看:105
本文介绍了大O(logn)日志是e吗?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

对于二进制搜索树类型的数据结构,我看到Big O表示法通常记为O(logn).在日志中使用小写字母"l",这是否意味着以自然对数描述的对数e(n)为对数?很抱歉这个简单的问题,但是我一直很难区分不同的隐式对数.

For binary search tree type of data structures, I see the Big O notation is typically noted as O(logn). With a lowercase 'l' in log, does this imply log base e (n) as described by the natural logarithm? Sorry for the simple question but I've always had trouble distinguishing between the different implied logarithms.

推荐答案

一旦以big-O()表示法表示,两者都是正确的.但是,在O()多项式的推导期间,对于 binary 搜索,只有log 2 是正确的.我认为这种区别是您提出问题的直观灵感.

Once expressed in big-O() notation, both are correct. However, during the derivation of the O() polynomial, in the case of binary search, only log2 is correct. I assume this distinction was the intuitive inspiration for your question to begin with.

据我所知,为您的示例编写O(log 2 N)更好,因为它可以更好地传达算法运行时间的推论.

Also, as a matter of my opinion, writing O(log2 N) is better for your example, because it better communicates the derivation of the algorithm's run-time.

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

In big-O() notation, constant factors are removed. Converting from one logarithm base to another involves multiplying by a constant factor.

由于常数因子,所以O(log N)等于O(log 2 N).

So O(log N) is equivalent to O(log2 N) due to a constant factor.

但是,如果您可以轻松地在答案中输入log 2 N,则这样做更具教学意义.在二叉树搜索的情况下,正确的是在导出big-O()运行时期间引入了log 2 N.

However, if you can easily typeset log2 N in your answer, doing so is more pedagogical. In the case of binary tree searching, you are correct that log2 N is introduced during the derivation of the big-O() runtime.

在将结果表示为big-O()表示法之前,区别非常重要.当推导要通过big-O表示法传递的多项式时,在此示例中,在应用O()表示法之前,使用log 2 N以外的对数是不正确的.一旦多项式用于通过big-O()表示法传递最坏情况的运行时,使用什么对数就无关紧要.

Before expressing the result as big-O() notation, the difference is very important. When deriving the polynomial to be communicated via big-O notation, it would be incorrect for this example to use a logarithm other than log2 N, prior to applying the O()-notation. As soon as the polynomial is used to communicate a worst-case runtime via big-O() notation, it doesn't matter what logarithm is used.

这篇关于大O(logn)日志是e吗?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆