是否有可能分裂的序列号为基础的中位值两组不排序？ [英] Is it possible to split a sequence of numbers into two groups based in median value without sorting?

问题描述

有一种算法来分割随机数序列分成两组基于对飞确定的中间值（没有对它们进行排序）？

Is there an algorithm to split a sequence of random numbers into two groups based on a median value determined on the fly(without sorting them)?

例。如果我有序列2-3-6-7-1-4-5，其结果必然是两个分离的群体：

Ex. If I have the sequence 2-3-6-7-1-4-5, the result would be two separated groups:

A）1 2 3

B）5 6 7

中值：4

推荐答案

是的，这可以做到的 O（N）

首先，如果我们已经知道了中位数，我们可以很容易地在 O（N）通过遍历序列，并比较各个值中位数一分为二的顺序。那么，我们如何找到中位数的 O（N）

First of all, if we already knew the median, we could easily split the sequence in two in O(n) by iterating the sequence and comparing each value with the median. So how do we find the median in O(n)?

的基本思想是使用快速排序的，但代替递归排序枢轴的两侧，排序仅包含位数的一半的（即，涵盖指数的一半⌈n/2⌉）。如果我们选择一个支点，保证快速排序的几何融合（如<一个href="http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22"相对=nofollow>中位数的中位数那样），那么我们整体的算法将是O（N）。

The basic idea is to use quicksort, but instead of recursively sorting both sides of the pivot, only sort the half that contains the median (ie. the half that encompasses the index ⌈n/2⌉). If our selection of a pivot guarantees geometric convergence of quicksort (like median-of-medians does), then our overall algorithm will be O(n).

让我们把我们的数组的当前大小的 K ，然后因降低中位数的中位数的 C - 即。我们的支点保证阵列收缩至少 C 的每一步的

Let's call the current size of our array k, and the reduction due to median-of-medians c - ie. our pivot guarantees the array shrinks by a factor of at least c each step

1. 使用估计数组的中位数中位数的中位数 - O（K）
2. 分区排列快速排序风格（与估计值作为我们的支点） - O（K）
3. 选择包含中位数的数组的一半（指数⌈n/2⌉）。这个新的子阵列将大小不超过 K / C 更大。重复步骤1和; 2递归，直到我们确定其位置原始数组中的元素⌈n/2⌉。

1. Estimate the median of the array using median-of-medians - O(k)
2. Partition the array quicksort-style (with the estimate as our pivot) - O(k)
3. Choose the half of the array containing the median (index ⌈n/2⌉). This new sub-array will have size no greater than k/c. Repeat steps 1 & 2 recursively until we've determined the element whose position in the original array is ⌈n/2⌉.

该算法的渐近运行时间为

The asymptotic running time of this algorithm is

2 O（N）+ 2 O（N / C）+ 2 O（N / C ² ）+ 2 O（N / C ³ ）+ ...
= O（N）

2 O(n) + 2 O(n/c) + 2 O(n/c²) + 2 O(n/c³) + ...
= O(n)

这篇关于是否有可能分裂的序列号为基础的中位值两组不排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！