P i*_*P i 26 sorting algorithm
我有一个n浮点数组,我希望返回前k(在我的情况下,n~100,k~10)
这个问题是否有已知的最佳解决方案路径？
有人可以提供C算法吗？
编辑:实际上这里有两个问题:排序和未排序.我对未分类感兴趣,应该更快!
小智 29
方法1
由于k很小,你可以使用锦标赛方法找到第k个最大的.Knuth的编程艺术,第3卷,第212页描述了这种方法.
首先在n-k + 2个元素上创建一个锦标赛.像淘汰赛网球锦标赛.首先你分成几对并比较成对的成员(就好像那两个玩了一个匹配而一个丢了).然后是获胜者,你再次分成两对,等等,直到你有一个胜利者.您可以将其视为树,获胜者位于顶部.
这与n-k + 1完全相比.
现在这些n-k + 2的获胜者不能成为你的第k个最大元素.考虑它在比赛中的路径P.
剩下的k-2现在选择一个,并沿着路径P向上,这将给你一个新的最大.基本上你有点重做锦标赛,前一个冠军被一个k-2元素取代.让P成为新赢家的道路.现在从k-3中选择另一个并按照新路径进行操作,依此类推.
在你耗尽k-2之后的最后,用-infinity替换最大的,并且锦标赛中最大的将是第k个最大的.你扔掉的元素是顶级的k-1元素.
这需要在大多数n - k + (k-1) [log (n-k+2)]比较中找到前k个.它虽然使用O(n)内存.
就比较数而言,这可能会超过任何选择算法.
方法2
作为替代方案,您可以维护k个元素的最小堆.
首先插入k个元素.然后对于数组的每个元素,如果它小于堆的min元素,则抛弃它.否则,删除堆的min并从数组中插入元素.
最后,堆将包含前k个元素.这将需要O(n log k)比较.
当然,如果n很小,只需对数组进行排序就足够了.代码也会更简单.
Phi*_*hby 10
简答:不.
更长的答案:是的,已知几种互不兼容的最佳解决方案.它取决于n,k以及您可以保证的阵列的属性.
如果您对数组一无所知,复杂性的下限显然是O(n),因为必须检查源数组的所有元素以查看它们是否适合前10位.如果您对源数组有任何了解,那么它就允许元素要安全地跳过,你应该使用这些知识.
类似地,上层复杂性边界是O(n.log(n)),因为您总是可以通过对数组进行排序(O(n.log(n))并返回前10个项目(O(1))来选择找到答案. .
线性搜索将每个项目与迄今为止发现的第十个最高项目进行比较,并将其插入到最高找到项目列表中的适当位置(如果需要),对于平均和最佳情况具有相似的复杂性,并且具有最差-O(kn)的情况明显优于O(n平方).对于您估计的尺寸,我希望这种方法表现良好.
如果n大得多(~10000)并且k以相同的比率增加,则可能值得实施快速选择算法.Quickselect可以更好地执行您想要的更多元素.但是,如果k没有按比例增加n,你应该坚持使用线性搜索.Quickselect和朋友修改原始数组,因此如果你不能这样做就不太适合,因为你需要更多的存储和大量的复制,而算法的复杂性不包括在内.
如果n很大(~1e20),你会想要从输入数组的多个分区中找到最大的k,然后从这些结果的集合中找到k-最大,这样你就不会试图分析更多一次可以装入内存的数据,并允许有效地并行操作.