在树结构的Big-O表示法中:为什么有些源引用O(logN)而有些源引用O(h)？

Question

在研究遍历二叉搜索树的任何算法的复杂性时,我看到两种表达同一事物的不同方式:

版本#1:最坏情况下的遍历算法比较树的每个高度一次; 因此复杂性是O(h).

版本#2:最坏情况下的遍历算法比较树的每个高度一次; 因此复杂性是O(logN).

在我看来,相同的逻辑在起作用,但不同的作者使用其中任何一个logN或h.有人可以向我解释为什么会这样吗？

Answer 1

搜索最坏情况时间的正确值是树是O(h),其中h是树的高度.如果您使用的是平衡搜索树(树的高度为O(log n)),则查找时间为最坏情况O(log n).也就是说,并非所有树木都是平衡的.例如,这是一个高度为n - 1的树:

1
 \
  2
   \
    3
     \
     ...
       \
        n

这里,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),因为它们可能是不平衡的.

希望这可以帮助!

Answer 2

如果你的二叉树是平衡的,所以每个节点只有两个子节点,那么树中的节点数将正好是N  = 2 ^h  - 1,所以高度是元素数量的对数(同样对于任何完整的n- tree树).

但是,任意的,不受约束的树可能看起来完全不同; 例如,它可以在每个级别只有一个节点,因此在这种情况下N  =  h.因此,高度是更一般的度量,因为它与实际比较有关,但在额外的平衡假设下,您可以将高度表示为元素数量的对数.