3

这个学期我有一个算法课程。一切都很好，直到我参加了关于订单统计的讲座。

这是该讲座的第一张幻灯片：

Order Statistics
Select the ith smallest of n elements (the
element with rank i).
• i = 1: minimum;
• i = n: maximum;
• i = ⎣(n+1)/2⎦ or ⎡(n+1)/2⎤: median.
Naive algorithm: Sort and index ith element.
Worst-case running time = Θ(n lg n) + Θ(1)
= Θ(n lg n)

我无法理解以下内容：

什么是订单统计？

在第 i 个最小的 n 元素上是什么意思？请我需要一个例子来知道什么是“ith”！

关于这些有什么简单的解释吗？

我所知道的是这与分而治之有关，因为下一张幻灯片就是关于它的:)。

4

2 回答 2

5

“顺序统计”是“按升序排序的 N 元素序列的第 K 个元素”的花哨名称。幻灯片的其余部分简单地说明了这个想法，解释了 1 阶统计量是序列中的最小元素，n 阶统计量是最大元素，n/2阶数统计量是中位数，等等。

于 2013-02-14T19:35:53.037 回答
1

它的顺序统计与数组中的第 i 个最小元素相同。例如，假设我们有一个数组 A[Size] ={ 3,4,-3,-2,0, 1,10,2,14} 并且我们想要对应于第 4 个的元素。排序统计，然后我们的函数或程序将返回值 1。此算法利用随机分区和对随机选择函数的递归调用。

伪代码如下：

 RSelect( Array[], p,r, i)

 if p == r
      return A[p]
 q = RandomPartition(Array[],p,r)
 k = q - p + 1
 if i == k // case that the pivot is the answer 
 return Array[q]

 else if i<k
     return RSelect(Array,p, q-1,i)
 else
     return RSelect(Array, q+1, r, i-k)

该算法是一种分治算法，它使用递归来分解问题，方法是选择在随机分区函数中完成的随机枢轴，以帮助对数组进行分区并抛出大于或小于枢轴的值，具体取决于关于第 i 个 Order 统计量是否大于或小于枢轴。例如，如果它的顺序统计量小于枢轴，它将丢弃大于枢轴的值。因为在 Partition 函数中返回的枢轴值在它的正确位置。

于 2015-09-22T22:58:05.963 回答