108

对于二叉搜索树类型的数据结构，我看到大 O 表示法通常记为 O(logn)。在 log 中使用小写的“l”，这是否意味着自然对数所描述的 log 底 e (n)？很抱歉这个简单的问题，但我一直无法区分不同的隐含对数。

4

7 回答 7

85

大 O 表示法不受对数底的影响，因为不同底的所有对数都由一个常数因子 相关，O(ln n)等价于O(log n)。

在此处输入图像描述

于 2009-10-15T00:31:38.287 回答
84

一旦用 big-O() 表示法表示，两者都是正确的。然而，在O() 多项式的推导过程中，在二分查找的情况下，只有 log 2是正确的。我认为这种区别是您提出问题的直观灵感。

另外，在我看来，写 O(log 2 N) 更适合您的示例，因为它可以更好地传达算法运行时的推导。

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

所以 O(log N) 等价于 O(log 2 N) 由于一个常数因子。

但是，如果您可以轻松地在答案中排版 log 2 N，那么这样做更具教学性。在二叉树搜索的情况下，在 big-O() 运行时的推导过程中引入 log 2 N 是正确的。

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

于 2009-10-15T00:32:40.370 回答
10

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

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))
于 2010-05-27T14:22:03.667 回答
9

它是什么基并不重要，因为 big-O 表示法通常只显示 的渐近最高阶n，因此常数系数会下降。由于不同的对数底相当于一个常数系数，所以它是多余的。

也就是说，我可能会假设对数基数为 2。

于 2009-10-15T00:31:23.180 回答
3

是的，当谈到大 O 表示法时，基数无关紧要。然而，在计算上，当面临真正的搜索问题时，它确实很重要。

在开发关于树结构的直觉时，了解二叉搜索树可以在 O(n log n) 时间内搜索是有帮助的，因为这是树的高度 - 也就是说，在具有 n 个节点的二叉树中，树深度为 O(n log n)（以 2 为底）。如果每个节点有三个孩子，仍然可以在 O(n log n) 时间内搜索树，但使用以 3 为底的对数。从计算上讲，每个节点的子节点数量会对性能产生很大影响（例如：链接文本）

享受！

保罗

于 2009-10-15T06:06:49.413 回答
3

首先，您必须了解函数 f(n) 为 O( g(n) ) 意味着什么。

正式定义是： *一个函数 f(n) 被称为 O(g(n)) 当且仅当 |f(n)| <= C * |g(n)| 当 n > k 时，其中 C 和 k 是常数。*

所以让 f(n) = n 的以 a 为底的对数，其中 a > 1 并且 g(n) = n 的以 b 为底的对数，其中 b > 1

注意：这意味着 a 和 b 的值可以是任何大于 1 的值，例如 a=100 和 b = 3

现在我们得到以下结果： n 的对数基数 a 被称为 O(n 的对数基数 b) 当且仅当 |n 的对数基数 a| <= C * |以 n 为底的对数 b| 每当 n > k

选择 k=0，并且 C= b 的对数基数 a。

现在我们的等式如下所示： |log base a of n| <= b 的以 a 为底的对数 * |n 的以 b 为底的对数| 每当 n > 0

注意右边，我们可以操作方程： = log base a of b * |log base b of n| = |n 的以 b 为底的对数| * log base a of b = |log base a of b^(log base b of n)| = |n 的以 a 为底的对数|

现在我们的等式如下所示： |log base a of n| <= |以n为底的对数| 每当 n > 0

无论 n、b 或 a 是什么值，除了它们的限制 a、b>1 和 n>0 之外，该等式始终为真。所以 n 的 log base a 是 O(log base b of n) 并且由于 a,b 无关紧要，我们可以简单地省略它们。

您可以在此处观看 YouTube 视频：https ://www.youtube.com/watch?v=MY-VCrQCaVw

你可以在这里阅读一篇文章：https ://medium.com/@randerson112358/omitting-bases-in-logs-in-big-o-a619a46740ca

于 2018-04-07T14:30:41.030 回答
1

从技术上讲，base 并不重要，但您通常可以将其视为 base-2。

于 2009-10-15T00:31:06.627 回答