arrays - 算法的最低限度是多少？

Question

让一个算法得到大小为n的未排序数组.让一个数字k<=n .该算法打印从 1 到 k(升序)的 k 个最小数字。算法的下限是多少(对于每个 k)？

1. Omega(n)
2. Omega(k*logn)
3. Omega(n*logk)
4. Omega(n*logn)
5. #1,#2 都正确。

现在，根据我的理解，如果我们想找到算法的下限，我们需要考虑最坏的情况。如果是这样，那么显然最坏的情况是 k=n。 .我们知道对数组进行排序的边界是Omega(nlogn)。所以正确答案是#4。

不幸的是，我错了，正确答案是#5。

为什么？

Answer 1

可以在 O(n + klogk) 中完成。

• 运行选择算法找到第 k 个最小元素 - O(n)
• 迭代并返回小于/等于 k ​​- O(n) 的元素
• 如果数组允许，可能需要另一次迭代重复，但仍然在 O(n) 中完成
• 最后，您需要在 O(klogk)
中对这些元素进行排序

很容易看出这个解决方案是最优的 - 不能比 O(klogk) 因子更好，因为否则分配 k=n 你可以更好地排序任何数组，至少线性扫描是必须找到要打印的所需元素。