在树结构的 Big-O 表示法中：为什么有些源引用 O(logN) 而有些源引用 O(h)？
在研究遍历二叉搜索树的任何算法的复杂性时，我看到两种不同的方式来表达同一件事：
版本#1：最坏情况下的遍历算法在树的每个高度比较一次；因此复杂度为O(h)。
版本#2：最坏情况下的遍历算法对树的每个高度进行一次比较；因此复杂度为O(logN)。
在我看来，相同的逻辑在起作用，但不同的作者使用 logN 或 h。有人可以向我解释为什么会这样吗？
In researching complexity for any algorithm that traverses a binary search tree, I see two different ways to express the same thing:
Version #1: The traversal algorithm at worst case compares once per height of the tree; therefore complexity is O(h).
Version #2: The traversal algorithm at worst case compares once per height of the tree; therefore complexity is O(logN).
It seems to me that the same logic is at work, yet different authors use either logN or h. Can someone explain to me why this is the case?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
最坏情况下搜索树的时间的正确值为 O(h)，其中 h 是树的高度。如果您使用平衡搜索树（树的高度为 O(log n)），则查找时间在最坏情况下为 O(log n)。也就是说，并非所有树都是平衡的。例如，这是一棵高度为 n - 1 的树：
这里，h = O(n)，因此查找时间为 O(n)。说查找时间也是 O(h) 是正确的，但在这种情况下 h ≠ O(log n)，并且声称查找时间是 O(log n) 是错误的。
简而言之，O(h) 是正确的界限。当高度至多为 O(log n) 时，O(log n) 是平衡搜索树中的正确界限，但并非所有树的查找时间都是 O(log n)，因为它们可能不平衡。
希望这有帮助！
The correct value for the worst-case time to search is tree is O(h), where h is the height of a tree. If you are using a balanced search tree (one where the height of the tree is O(log n)), then the lookup time is worst-case O(log n). That said, not all trees are balanced. For example, here's a tree with height n - 1:
Here, h = O(n), so the lookup is O(n). It's correct to say that the lookup time is also O(h), but h ≠ O(log n) in this case and it would be erroneous to claim that the lookup time was O(log n).
In short, O(h) is the correct bound. O(log n) is the correct bound in a balanced search tree when the height is at most O(log n), but not all trees have lookup time O(log n) because they may be imbalanced.
Hope this helps!
如果您的二叉树是平衡的，每个节点都有两个子节点，那么树中的节点数将恰好是 N = 2h − 1，因此高度是元素数量的对数（对于任何完整的n二叉树也类似）。
然而，一棵任意的、不受约束的树可能看起来完全不同；例如，它可以在每一层只有一个节点，因此在这种情况下N= h。因此，高度是更通用的度量，因为它与实际比较相关，但在额外的平衡假设下，您可以将高度表示为元素数量的对数。
If your binary tree is balanced so that every node has exactly two child nodes, then the number of nodes in the tree will be exactly N = 2h − 1, so the height is the logarithm of the number of elements (and similarly for any complete n-ary tree).
An arbitrary, unconstrained tree may look totally different, though; for instance, it could just have one node at every level, so N = h in that case. So the height is the more general measure, as it relates to actual comparisons, but under the additional assumption of balance you can express the height as the logarithm of the number of elements.
O(h) 表示已排序但不平衡的二叉树
O(logn) 表示已排序且平衡的二叉树
O(h) would refer to a binary tree that is sorted but not balanced
O(logn) would refer to a tree that is sorted and balanced
这是同一件事的两种表达方式，因为高度为“h”的平均平衡二叉树将具有大约 2^h 个节点。
根据上下文，高度或 #nodes 可能更相关，因此您将看到引用的内容。
It's sort of two ways of saying the same thing, because your average balanced binary tree of height 'h' will have around 2^h nodes.
Depending on the context, either height or #nodes may be more relevant, and so that's what you'll see referenced.
因为平衡树的 (h)eight 随着元素数 (N) 的对数而变化
because the (h)eight of a balanced tree varies as the log of the (N)umber of elements