做o(h)算法n次的时间复杂度。

Question

当h是BST中节点高度的n倍（树中元素的数量）时，做O(h)算法的时间复杂度是多少，我相信是O(n)而不是O(n*h)，但我不知道如何证明。

在O(h)中工作的具体算法是寻找BST中元素的In-order predecessor。

Answer 1

在任何BST中，计算顺序继承者n次的成本是O(n)。要看到这一点，请计算你接触树中每个边的次数。当你第一次探索一个子树时，你会向下传递一次边缘，在你离开子树后再传递一次。总的来说，这意味着你最多接触每个边缘两次，所以完成的总工作是O(n)。

需要注意的是，一般来说，你可以将在高度为h的BST上执行n O(h)-时间的成本上限为O(hn)，这样永远不会低估事情。然而，如果你更具体地了解你所使用的算法，就像在这种情况下，你可以得到一个更严格的约束。

Answer 2

O(n²).

二元搜索树是不平衡的，这意味着一个节点的高度可以等于树的节点数，因此O（n²）。