完全平衡二叉树的复杂性
Complexity of Perfectly Balanced Binary Tree
我的场景是包含整数的完美平衡二叉树。
我搜索并找到了许多关于 best/worst 二叉树案例场景的解释。最好的情况是 O(1)（在根中找到目标），最坏的情况是 O(log(n))（树的高度）。
我几乎没有找到关于计算 平均 复杂度的信息。我能找到的最佳答案是 O(log(n)) - 1，但我想我不太明白（如果正确的话）这个平均情况是如何计算的。
此外，搜索不在树中的整数是否会产生相同的复杂性，我认为会，但任何鼓励都是值得赞赏的。
假设我们有一个包含 n = 2<sup>k</sup> 个整数的完美平衡二叉树，所以深度是 log₂(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(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 表示法中 O(x) 和 O(x±c) 对于任何常量值都是相同的 c.
路途遥远
现在让我们尝试计算树中包含的随机（均匀分布）整数 X 的平均情况，并命名第 i-th“行”上的整数集树T<sub>i</sub>。 T<sub>i</sub> 包含 2<sup>i</sup> 元素。 T<sub>0</sub>表示根。
在第i行选择一个整数的概率是P(X ∈ T<sub>i</sub>) = 2<sup>i</sup>/n = 2<sup>i-k</sup>.
要在行 i 上找到一个整数，需要 O(2<sup>i</sup>) = 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)-1) = O(log(n))。
值不在树中
如果值不在树中，则必须遍历整棵树。在 log(n) 步之后，您找到了一片叶子。如果该值等于您输入的值，则您已找到要搜索的内容。如果不是，您知道，您搜索的值不包含在树中。因此，如果您搜索不在树中的值，它将需要 O(log(n)).
我的场景是包含整数的完美平衡二叉树。
我搜索并找到了许多关于 best/worst 二叉树案例场景的解释。最好的情况是 O(1)（在根中找到目标），最坏的情况是 O(log(n))（树的高度）。
我几乎没有找到关于计算 平均 复杂度的信息。我能找到的最佳答案是 O(log(n)) - 1，但我想我不太明白（如果正确的话）这个平均情况是如何计算的。
此外，搜索不在树中的整数是否会产生相同的复杂性，我认为会，但任何鼓励都是值得赞赏的。
假设我们有一个包含 n = 2<sup>k</sup> 个整数的完美平衡二叉树，所以深度是 log₂(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(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 表示法中 O(x) 和 O(x±c) 对于任何常量值都是相同的 c.
路途遥远
现在让我们尝试计算树中包含的随机（均匀分布）整数 X 的平均情况，并命名第 i-th“行”上的整数集树T<sub>i</sub>。 T<sub>i</sub> 包含 2<sup>i</sup> 元素。 T<sub>0</sub>表示根。
在第i行选择一个整数的概率是P(X ∈ T<sub>i</sub>) = 2<sup>i</sup>/n = 2<sup>i-k</sup>.
要在行 i 上找到一个整数，需要 O(2<sup>i</sup>) = 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)-1) = O(log(n))。
值不在树中
如果值不在树中，则必须遍历整棵树。在 log(n) 步之后，您找到了一片叶子。如果该值等于您输入的值，则您已找到要搜索的内容。如果不是，您知道，您搜索的值不包含在树中。因此，如果您搜索不在树中的值，它将需要 O(log(n)).