我试图找出对某些数据聚合（比如数组）计算 top-k 查询的最佳方法。我曾经认为最好的方法是遍历数组并维护大小为 k 的堆或平衡二叉树，利用它来计算 top-k 值。现在，我遇到了据说运行得更快的选择算法。我了解选择算法的工作原理以及如何实现它，我只是对它在 O(n) 中的运行方式有点困惑。我觉得为了让它在 O(n) 中运行，你必须非常幸运。如果您继续选择一个随机枢轴点并围绕它进行分区，那么很可能您最终会在偶然发现第 k 个索引之前对几乎整个数组进行排序。是否有任何优化，例如可能不选择随机枢轴？或者我在大多数情况下维护堆/树方法是否足够好。
1 回答
1
你在说的是快速选择，也称为霍尔的选择算法。
它确实具有O(n)平均情况下的性能，但其最坏情况下的性能是.O(n2)
与快速排序一样，快速选择具有良好的平均性能，但对选择的枢轴很敏感。如果选择了好的枢轴，即始终将搜索集减少给定分数的枢轴，则搜索集的大小呈指数下降，并且通过归纳（或对几何级数求和），人们会看到性能是线性的，因为每个步骤都是线性的，并且总时间是这个的常数倍（取决于搜索集减少的速度）。但是，如果始终选择错误的枢轴，例如每次仅减少一个元素，那么最坏情况下的性能是二次的：.
O(n2)
在选择支点方面：
最简单的解决方案是选择一个随机枢轴，这会产生几乎确定的线性时间。确定性地，可以使用中值 3 枢轴策略（如在快速排序中），这在部分排序的数据上产生线性性能，这在现实世界中很常见。然而，人为的序列仍然会导致最坏情况的复杂性。David Musser 描述了一个“3 中位数杀手”序列，允许对该策略进行攻击，这是他的introselect算法的一个动机。
即使在最坏的情况下，也可以通过使用更复杂的枢轴策略来确保线性性能；这是在中位数算法中完成的。但是，计算主元的开销很高，因此在实践中通常不使用。可以将基本的快速选择与中值的中值结合起来作为后备，以获得快速的平均情况性能和线性最坏情况性能；这是在 introselect 中完成的。
（引自维基百科）
因此，您很有可能O(n)通过随机枢轴获得性能，但是，如果k很小n或很大，或者如果您不太可能，O(n log k)使用大小k堆或 BST 的解决方案可能会胜过此操作。
我们不能肯定地告诉你哪个会更快——这取决于 (1) 确切的实现，(2) 运行它的机器，(3) 的确切大小，n最后k是 (4) 实际数据. 该O(n log k)解决方案应该足以满足大多数目的。
于 2014-01-17T01:20:21.243 回答