在大O符号的树形结构：为什么一些消息来源指O（logN）的，有的为O（H） [英] In Big-O notation for tree structures: Why do some sources refer to O(logN) and some to O(h)?

问题描述

在任何算法遍历二叉搜索树研究的复杂性，我看到了两种不同的前preSS同样的事情：

In researching complexity for any algorithm that traverses a binary search tree, I see two different ways to express the same thing:

版本＃1：遍历算法在最坏的情况下，比较每一次树的高度;因此，复杂性是 0（H）。

Version #1: The traversal algorithm at worst case compares once per height of the tree; therefore complexity is O(h).

版本＃2：遍历算法在最坏的情况下，比较每一次树的高度;因此，复杂性是 O（logN）的。

Version #2: The traversal algorithm at worst case compares once per height of the tree; therefore complexity is O(logN).

在我看来，同样的逻辑在起作用，但不同的作者请使用 logN个或 ^ h 。有人可以给我解释一下为什么是这样的情况？

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?

推荐答案

如果您的二叉树是平衡的，这样每个节点正好有两个子节点，在树中的节点将是随后数不完全的 N ＆NBSP; =＆NBSP; 2 ^ħ的＆NBSP;＆减去;＆NBSP; 1，因此高度是元件的数量的对数（以及类似地为任何完整的 N 的进制树）。

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 = 2^h − 1, so the height is the logarithm of the number of elements (and similarly for any complete n-ary tree).

这是随心所欲，不受约束的树可能看起来完全不同，虽然;例如，它可以只是在每一级有一个节点，所以 N 的＆NBSP; =＆NBSP; ħ的在这种情况下。所以高度是更一般的量度，因为它涉及到实际比较，但下平衡的附加假设可以前preSS的高度的元件的数目的对数。

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符号的树形结构：为什么一些消息来源指O（logN）的，有的为O（H）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！