Ida*_*dan 23 sorting algorithm big-o
这是我在网上发现的一个有趣的问题.给定一个包含n数字的数组(没有关于它们的信息),我们应该在线性时间内预处理数组,这样我们就可以及时返回k最小的元素O(k),当我们给出一个数字时1 <= k <= n
我和一些朋友一直在讨论这个问题,但没有人能找到解决方案; 任何帮助,将不胜感激!
Kar*_*ath 14
对于预处理步骤,我们将在同一数据集上多次使用基于分区的选择.
使用算法找到第n/2个数字.现在,数据集被分为两个部分,下部和上部.在下半部再次找到中点.在它的下部分区做同样的事情等等......总的来说,这是O(n)+ O(n/2)+ O(n/4)+ ... = O(n).
现在,当您必须返回k个最小元素时,搜索最近的x < k,其中x是分区边界.它下面的所有东西都可以返回,从下一个分区你必须返回k - x数字.由于下一个分区的大小为O(k),因此为第k个x数字运行另一个选择算法将返回其余分区.