选择算法运行时

我想弄清楚最优化的方式来计算一些聚合的数据顶部k查询，可以说一个数组。我曾经认为最好的方法是遍历数组并维护一个k大小的堆或平衡二叉树，利用它来计算top-k值。现在，我运行了选择算法，该算法运行速度更快。我理解选择算法是如何工作的以及如何实现它，我只是对它在O（n）中的运行方式感到有点困惑。我觉得为了让它在O（n）中运行，你必须非常幸运。如果你不断挑选一个随机支点并对其进行分区，那么很可能就是你最终基本上排序了整个阵列，然后才绊倒你的第k个索引。是否有任何优化，如可能不选择随机数据透视？或者，我在大多数情况下维护堆/树方法已经足够好了。选择算法运行时

来源

2014-01-16 AyBayBay

挑剔的关键是这里的诀窍。这就是所谓的寻找“中位数”。你可以看http://en.wikipedia.org/wiki/Median_of_medians#Algorithm – tgpatel

@tgpatel解释和算法感谢您的建议，我通读它，它是有道理的。然而，这是相当复杂的，不会更简单，更优雅的解决方案是在维护数据时保持自我平衡BST或K大小的二进制堆。最差情况下的表现NlogK与选择结合算法的线性表现并无太大差别。这个选择与Medians中值并不完全是O（N），这是一个求和序列，当在大O中分析时，仍然在时间N中。我认为你得到的总和的最终值不会离NlogK太远。 – AyBayBay

你在说什么有quickselect, also known as Hoare's selection algorithm。

它确实有O(n)平均情况下的性能，但其最坏情况下的性能是O(n²)。

与快速排序一样，快速选择具有良好的平均性能，但对选择的枢轴很敏感。如果选择了良好的枢轴，这意味着通过给定分数持续减少搜索集，那么搜索集按指数规律减小尺寸，并且通过归纳（或求和几何系列），可以看到性能是线性的，因为每个步骤是线性的并且总的时间是这个常数（取决于搜索集减少的速度）。但是，如果始终选择不良枢轴，例如每次只减少一个元素，则最差情况的性能是二次的：O(n²)。

在选择枢轴的术语：

的最简单的解决办法是选择一个随机枢轴，其产生almost certain线性时间。确定性地，可以使用3位数中值策略（如在quicksort中），该策略在部分排序的数据上产生线性性能，这在现实世界中很常见。但是，人为序列仍然可能导致最坏情况的复杂性; David Musser描述了一个“3中位数杀手”序列，允许针对该策略发起攻击，这是他的introselect算法的动机之一。

即使在最糟糕的情况下，通过使用更复杂的枢轴策略，也可以保证线性性能;这在median of medians算法中完成。然而，计算枢轴的开销很高，因此在实践中通常不会使用。可以将基本快速选择和中位数作为回退来获得快速平均情况表现和线性最坏情况表现;这是在内部完成的。

^{（从Wikipedia引号）}

所以你很可能得到O(n)性能随机支点，但是，如果k小，n较大，或者如果你只是不大，使用k堆或BST的O(n log k)解决方案可能会胜过这一点。（1）确切的实施方式，（2）机器的运行方式，（3）确切的尺寸n和k，以及最终确定的尺寸（4）实际数据。对于大多数目的来说，O(n log k)解决方案应该足够了。

来源

2014-01-17 01:20:21 Dukeling

+1。事实上，当k相对于n很小时，O（n log k）堆选择算法*的性能优于Quickselect。我曾经做过相当广泛的测试。见http://blog.mischel.com/2011/10/25/when-theory-meets-practice/ –

选择算法运行时

回答

相关问题