大O符号日志基地2或登录基地10 [英] Big O notation Log Base 2 or Log Base 10

问题描述

在文章/问题状态，该算法的大O运行时间为O（LOGN）。

When articles/question state that the Big O running time of the algorithm is O(LogN) .

例如快速排序已经邻一个大O运行时间（LOGN），其中就以10为底，但二叉树的高度是O（LOGN + 1）它是日志基地2

For example Quicksort has a Big O running time of O (LogN) where the it is Log base 10 but Height of binary tree is O(LogN+1) where it is Log base 2

问题

1）我很困惑在是否是它以10为底或登录基地2个不同的文章使用不同的基地，他们对数。

1)I am confused over whether is it Log base 10 or Log base 2 as different articles use different bases for their Logarithm .

2）是否有所作为，如果其日志基地2个或登录基地10 ??

2) Does it make a difference if its Log base 2 or Log base 10??

3），我们可以假设它意味着以10为底，当我们看到O（LOGN）???

3)Can we assume it mean Log base 10 when we see O(LogN)???

推荐答案

我觉得也无所谓什么是日志的基地为相对复杂性是一样的，不论使用的基地。

I think it does not matter what is the base of the log as the relative complexity is the same irrespective of the base used.

所以，你可以把它看成是为O（log ₂ X）= O（日志 ₁₀ X）

So you can think of it as O(log₂X) = O(log₁₀X)

另外要提的是对数由某个常数相关的。

Also to mention that logarithms are related by some constant.

所以

log₁₀（ X 的）=log₂（ X 的）/log₂（10）

So

log₁₀(x) = log₂(x) / log₂(10)

所以大部分的时间我们一般不考虑复杂的分析常数，因此，我们说，该基地没有关系。

So most of the time we generally disregard constants in complexity analysis, and hence we say that the base doesn't matter.

另外，你可能会发现，该基地被认为是2大部分时间像合并排序。树有高度log₂ñ，由于节点有两个分支。

Also you may find that the base is considered to be 2 most of the time like in Merge Sort. The tree has a height of log₂ n, since the node has two branches.

1）我很困惑在是否是它以10为底或登录基地2作为   不同的文章使用不同的基地，他们对数。

1)I am confused over whether is it Log base 10 or Log base 2 as different articles use different bases for their Logarithm .

所以上述碱这一变化所解释并不重要。

So as explained above this change of base doesn't matter.

2）是否有所作为，如果其日志基地2个或登录基地10 ??

2) Does it make a difference if its Log base 2 or Log base 10??

没有也没关系。

3），我们可以假设它意味着以10为底，当我们看到O（LOGN）???

3)Can we assume it mean Log base 10 when we see O(LogN)???

是的，你可以假设前提是你知道的基地转换规则。

Yes you can assume that provided you know the base conversion rule.

这篇关于大O符号日志基地2或登录基地10的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！