完美平衡二叉树的复杂度

Question

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

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

我几乎没有发现关于计算平均复杂度的信息。我能找到的最佳答案是O(log(n)) - 1，但我想我不太明白（如果正确的话）这个平均情况是如何计算的。

此外，搜索不在树中的整数是否会产生相同的复杂性，我认为会，但任何煽动都值得赞赏。

Answer 1

假设我们有一个包含整数的完美平衡二进制树，因此深度为。n = 2klog?(n) = k

正如你所说，最好和最坏的情况是，O(1)和O(log(n))。

捷径

让我们X从二叉树中选择一个随机整数（均匀分布）。树的最后一行包含与第一k-1行相同数量的整数。概率1/2 X在第一k-1行，所以我们最多需要几个O(k-1) = O(log(n)-1)步骤来找到它。并且还有概率1/2 X在最后一行，我们需要O(k) = O(log(n))步骤。

我们总共得到

E [X] ? P(X 行 ? k-1)?O(log(n)-1) + P(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 符号中O(x)并且O(x±c)对于任何常量 value 都是相同的c。

很长的路要走

现在让我们尝试计算包含X在树中的随机（均匀分布）整数的平均情况，并让我们命名树的i第 -th“行”上的整数集。包含元素。表示根。TiTi2iT0

在第 i 行中选择一个整数的概率是。P(X ? Ti) = 2i/n = 2i-k

要在行上找到一个整数，i它需要采取步骤。O(2i) = O(i)

所以预期的步数是

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

为了简化这一点，我们使用

O(i)?2 i-k + O(i+1)?2 i+1-k ? O(i)?2 i+1-k + O(i+1)?2 i+1-k ? O(i+1)?2 i+2-k

这导致我们

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

因为k = log(n)，我们看到平均情况在O(log(n)-1) = O(log(n)).

值不在树中

如果值不在树中，则必须遍历整棵树。经过log(n)几步，你找到了一片叶子。如果该值等于您的输入，则您已经找到了您要搜索的内容。如果不是，您知道，您搜索的值不包含在树中。因此，如果您搜索不在树中的值，它将需要O(log(n)).