的中值选择最优值 - 3元块VS 5元块？ [英] Optimal median of medians selection - 3 element blocks vs 5 element blocks?

问题描述

我在一个快速排序变实现基于<工作href="http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm"相对=nofollow>选择算法以选择一个好的主元。传统智慧似乎是划分阵列分为5-元件块，每次取的中值，然后递归相同阻挡方法应用到所得到的位数，以得到一个位数的中值。

I'm working on a quicksort-variant implementation based on the Select algorithm for choosing a good pivot element. Conventional wisdom seems to be to divide the array into 5-element blocks, take the median of each, and then recursively apply the same blocking approach to the resulting medians to get a "median of medians".

什么是困惑我是5元块，而不是3元块的选择。随着5元块，在我看来，你执行 N / 4 = N / 5 + N / 25 + N / 125 + N / 625 + ... 中位数-of-5操作，而3元块，执行 N / 2 = N / 3 + N / 9 + N / 27 + N / 81 + ... 中位数的3操作。作为每一个中值-5为6的比较，每个中位数的3 2的比较，这导致了 3 * N / 2 使用比较平均，OF- 5和 N 用中位数的3比较。

What's confusing me is the choice of 5-element blocks rather than 3-element blocks. With 5-element blocks, it seems to me that you perform n/4 = n/5 + n/25 + n/125 + n/625 + ... median-of-5 operations, whereas with 3-element blocks, you perform n/2 = n/3 + n/9 + n/27 + n/81 + ... median-of-3 operations. Being that each median-of-5 is 6 comparisons, and each median-of-3 is 2 comparisons, that results in 3*n/2 comparisons using median-of-5 and n comparisons using median-of-3.

任何人都可以解释这种差异，什么动机，使用5元块可能是什么？我不熟悉的应用这些算法的惯例，所以也许有一些方法可以切割出一些措施，仍然可以得到足够接近中位数，以保证良好的支点，而这种方法效果更好，5元块？

Can anyone explain this discrepancy, and what the motivation for using 5-element blocks could be? I'm not familiar with usual practices for applying these algorithms, so maybe there's some way you can cut out some steps and still get "close enough" to the median to ensure a good pivot, and that approach works better with 5-element blocks?

推荐答案

原因是，通过选择3个街区，我们可能会失去使用一个O（n）时间算法的保障。

The reason is that by choosing blocks of 3, we might lose the guarantee of having an O(n) time algorithm.

有关的5块，时间复杂度为

For blocks of 5, the time complexity is

T（N）= T（N / 5）+ T（7N / 10）+ O（N）

T(n) = T(n/5) + T(7n/10) + O(n)

有关的3个街区，它出来是

For blocks of 3, it comes out to be

T（N）= T（N / 3）+ T（2π/ 3）+ O（N）

T(n) = T(n/3) + T(2n/3) + O(n)

检查了这一点：<一href="http://www.cs.berkeley.edu/~luca/w4231/fall99/slides/l3.pdf">http://www.cs.berkeley.edu/~luca/w4231/fall99/slides/l3.pdf

这篇关于的中值选择最优值 - 3元块VS 5元块？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！