algorithm - 通过每个元素的 log(n) 比较找到最少的 n 个元素

Question

我需要编写一个算法来找到 n 个元素的最小值：

1. n-1 个比较。
2. 每个元素仅执行 log(n) 比较。

我想到了选择搜索算法，但我认为它比较每个元素超过 log(n) 次。

有任何想法吗？谢谢！

Answer 1

您可以将选择过程视为一场锦标赛：

1. 第一个元素与第二个元素进行比较，第三个元素与第四个元素进行比较，依此类推。
2. 比较的赢家是较小的元素。
3. 所有获胜者以相同的方式参加下一轮，直到剩下一个元素。剩下的元素是最小的。

伪代码

我将给出递归解决方案，但您也可以迭代地实现它。

smallestElement(A[1...n]):
    if size(A) == 1:
        return A[1]
    else
        return min(smallestElement(A[1...n/2], smallestElement(A[n/2 + 1...n]))

递归具有深度 logn，因为在每个级别上，我们将输入的大小除以 2，因此锦标赛的获胜者参与 logn 比较，并且没有一个元素参与更多比较。