2

假设我们有一个最初为空的 BST，我在其中执行 n 次任意插入，我如何找到这个 BST 的平均高度？表达式/伪代码将是（如果我没记错的话）：

H(T) = 1 + max(H(T.left), H(T.right))

我对此的递归关系的猜测是T(n) = 1 + 2*T(n/2)，但我不确定这是否正确。

现在这是我的困境，如果我的递归关系是正确的，我如何计算我的平均高度算法的平均复杂度？

4

2 回答 2

0

T(n/2)+c 其中 c 是某个常数，我们将数组分成两部分，但我们只使用单个部分进行搜索。如果 out ans 大于中间值，那么我们只搜索 (mid+1 .....j) 如果它小于中间值，那么我们只在(i.....mid) 中搜索，所以，有时我们只使用单个子数组

于 2014-07-29T17:23:33.970 回答
0

一般来说，平均情况分析更复杂，您不能真正使用在正常最坏情况证明中使用的相同大 O 技术。虽然您对高度的定义是正确的，但将其转换为递归可能会比这更复杂。首先，您可能的意思是T(n) = 1 + T(n/2)（这将给出 O(log n) 高度，而您的版本给出 O(n)）然后，没有任何东西可以保证值在左右之间均匀分割为 50-50。

如果你稍微搜索一下，你会发现在 BST 的平均高度上有很多材料。例如，我得到的一个结果是，随着 n 的增长，BST 的预期高度趋向于 4.3 * (log n)，但要经过大量复杂的数学运算才能到达那里。

于 2012-05-23T17:34:31.590 回答