Asymptotics Problems Solutions

渐近性问题解答

1. 错误。最坏情况是 $\Theta(N)$，对于一个退化的二叉搜索树

2. 错误。最坏情况是 $\Theta(N)$

3. 错误。最佳情况是 $\Theta(\log(N))$，对于一个平衡的二叉搜索树

4. 正确

5. 正确（记住，除非另有说明，否则大O不一定是渐近紧确的！）

6. 错误。在最佳情况下，这些节点靠近根。请注意，如果 C 和 K 是随机选择的，那么在均摊情况下（即均摊分析），这是正确的，因为树中平均节点的深度由以下总和给出： $\sum\_{h=1}^{\lg n} \frac{h2^h}{N} \in \Theta(\log N)$

7. mystery 找到 BST 中排名第 z 的元素（从 1 开始索引）。它通过计算左子树中的元素数量来实现这一点，然后判断左子树的元素数量是否大于或小于 z，从而转到右子树或左子树。请注意，numLeft 将花费与左子树中节点数量成正比的时间，因此一个递归子调用中的工作量是 $\Theta(\text{左子树中的节点数量})$。

树上没有条件，所以我们必须考虑树是平衡的、左倾斜的和右倾斜的情况。最佳情况是树的根恰好是排名第 z 的元素，在这种情况下，它将花费 $\Theta(\text{左子树中的节点数量})$ 时间（因为没有递归调用）。

• 平衡树：左子树中有 $\frac{N}{2} - 1$ 个节点， 因此，在最佳情况下（当 z == N / 2 时），运行时为 $\Theta(N)$。
• 左倾的树：左子树中有 $N - 1$ 个节点， 因此，在最佳情况下（当 z == N 时），运行时为 $\Theta(N)$。
• 右倾的树：左子树中有 $0$ 个节点，因此在最佳情况下（当 z == 1 时），运行时为 $\Theta(1)$。

因此，最佳情况运行时为 $\Theta(1)$。

最坏情况发生在我们需要一直遍历到树的叶子节点时。

• 平衡树：对于第一个递归调用，左子树中大约有 $\frac{N}{2}$ 个节点，然后第二个递归调用的左子树中大约有 $\frac{N}{4}$ 个节点，依此类推，直到我们到达叶子节点。这意味着最坏情况下的运行时是 $\frac{N}{2} + \frac{N}{4} + \frac{N}{8} + \dots + 1 \in \Theta(N)$（当 z == 1 时）。
• 左倾的树：在这种情况下，每个递归调用都会使左子树中的节点比父节点少一个。其总和为 $N + (N-1) + (N-2) + \dots + 1 \in \Theta(N^2)$（当 z == 1 时）。
• 右倾的树：在每次递归调用中，左子树中有 $0$ 个节点，并且树的高度为 $N$，因此最坏情况下的运行时为 $\Theta(N)$（当 z == N 时）。

综上所述，最坏情况下的运行时为 $\Theta(N^2)$。

总结：最佳情况：$\Theta(1)$。最坏情况：$\Theta(N^2)$。