题10

题10

题目

Q:在由 路归并构建的败者树中选取一个关键字最小的记录,则所需时间为 ( ).
A. B. C. D. 以上都不对

分析

A:在败者树中选取最小关键字的时间复杂度取决于败者树的高度，所需时间为 。

解

C
你对败者树的理解基本正确，最小元素确实在树顶。但是，选择最小元素后，我们需要更新败者树，使其保持正确性，这个过程的开销不能忽略。
让我们一步一步分析选取最小关键字后的更新操作，找出你的误解：

1. 初始状态： 最小元素在败者树的根节点，可以直接获取，时间复杂度O(1)。
2. 选择最小值后： 我们需要从败者树中移除这个最小值，并将对应归并段的下一个元素补充到败者树中。
3. 更新败者树： 为了保证败者树的性质，新插入的元素需要沿着从叶节点到根节点的路径进行比较和调整，这个路径的长度是 （因为败者树是一棵完全二叉树）。
   • 每次比较都需要更新败者树中存储的败者信息。
   • 这个更新过程的时间复杂度是 。
     你的误解在于：

• 只考虑了获取最小值的开销，而忽略了更新败者树的开销。
  实际情况：
  在 k 路归并的败者树中，选取一个关键字最小的记录，总的时间复杂度是 C. ， 因为它包含：
• 获取最小值: O(1)
• 更新败者树: O(log k)