完全平衡二叉树的复杂度

Question

我的情景是包含整数的完美平衡二叉树。

我已经搜索并找到了许多关于二叉树最佳/最坏情况的解释。最佳情况是 O(1)（在根中找到目标），最坏情况是 O(log(n))（树的高度）。

我几乎没有找到有关计算平均复杂度的信息。我能找到的最好答案是 O(log(n)) - 1，但如果这个答案正确的话，我似乎不太理解如何计算平均情况。

此外，查找不在树中的整数是否会产生相同的复杂度，我认为会，但任何见解都将不胜感激。

- user1726845

---

最容易理解log(n)复杂度的答案：https://dev59.com/q3E95IYBdhLWcg3wb9hb#13093274 - 2cupsOfTech

Answer 1

假设我们有一个包含 n = 2k 个整数的完美平衡二叉树，所以深度为 log₂(n) = k。

最好和最坏情况是，如你所说，分别为 O(1) 和 O(log(n))。

简短方式

从二叉树中选择一个随机整数 X（均匀分布）。最后一行树包含的整数与前面的 k-1 行加在一起相等。如果 X 在第一行到第 k-1 行，那么我们最多需要 O(k-1) = O(log(n)-1) 步才能找到它，概率为 1/2。同样地，如果 X 在最后一行，那么我们需要 O(k) = O(log(n)) 步。

总之，我们得到：

E[X] ≤ P(row of X ≤ k-1)⋅O(log(n)-1) + P(row of X = k)⋅O(log(n))
     = 1/2⋅O(log(n)-1) + 1/2⋅O(log(n))
     = 1/2⋅O(log(n)-1) + 1/2⋅O(log(n)-1)
     = O(log(n)-1)

注意：这有点丑陋，但在 O-notation 中，对于任何常量值 c，O(x) 和 O(x±c) 是相同的。

详细方式

现在让我们尝试计算包含在树中的随机（均匀分布）整数 X 的平均情况，并将树上的第 i 行整数的集合命名为 Ti。 Ti 包含 2i 个元素。 T0 表示根。

选择第 i 行的整数的概率是 P(X ∈ Ti) = 2i/n = 2i-k。

找到位于第 i 行的整数需要 O(2i) = O(i) 步。

因此，期望步数为

E[X] = Σi=0,...,k-1 O(i)⋅2i-k.

为简化计算，我们使用

O(i)⋅2i-k + O(i+1)⋅2i+1-k ≤ O(i)⋅2i+1-k + O(i+1)⋅2i+1-k ≤ O(i+1)⋅2i+2-k

这导致我们得出

E[X] = Σi=0,...,k-1 O(i)⋅2i-k ≤ O(k-1)⋅2⁰

由于 k = log(n)，我们可以看到平均情况下的时间复杂度为 O(log(n))。

不在树中的值

如果该值不在树中，则必须遍历整棵树。经过 log(n) 步后，您会找到一个叶子节点。如果该值等于您的输入，则已找到您要查找的内容。如果不是，则知道您要查找的值不包含在树中。因此，如果搜索不存在于树中的值，它将花费 O(log(n)) 的时间复杂度。

- AbcAeffchen