渐进分析题解决方案

渐近分析习题解答

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)\) 给出

{:start=”7”} 7. mystery finds the z th largest element in the 二叉搜索树 (indexed from 1). It does th是 by calculating the number of elements in the left subtree, then going to the right or left subtree depending on whether we have too many elements in the left subtree or not enough. 请注意 numLeft will take proportional time to the number of nodes in the left subtree, so the amount of work in 一 recursive subcall 是 $\Theta(\text{number of nodes in left subtree})$.

对树没有任何条件，所以我们必须考虑树是茂盛的、左细长的和右细长的情况。最好情况是当树的根正好是第 z 大的元素时，在这种情况下，它将花费 $\Theta(\text{左子树中的节点数量})$ 时间（因为没有递归调用）。

• 茂盛的树：左子树中有 $\frac{N}{2} - 1$ 个节点，所以最好情况下的运行时间是 $\Theta(N)$（当 z == N / 2 时）。
• 细长的树（左）：左子树中有 $N - 1$ 个节点，所以最好情况下的运行时间是 $\Theta(N)$（当 z == N 时）。
• 细长的树（右）：左子树中有 $0$ 个节点，所以最好情况下的运行时间是 $\Theta(1)$（当 z == 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)$。