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)

次のことがわかりません。

注文統計とは何ですか？

n個の要素の中でi番目に小さいものとはどういう意味ですか？「i番目」とは何かを知るための例が必要です！

これらについて簡単な説明はありますか？

私が知っているのは、次のスライドがそれについてであるため、これは分割統治に関連しているということだけです:)。

4

2 に答える 2

5

「順序統計」は、「昇順でソートされたN要素シーケンスのK番目の要素」の空想的な名前です。n/2スライドの残りの部分は、1次統計量がシーケンス内の最小要素、n次統計量が最大要素、順序統計量が中央値などであることを説明する、アイデアを簡単に示しています。

于 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統計がピボットよりも大きいか小さいかについて。たとえば、it順序統計がピボットよりも小さい場合、ピボットよりも大きい値は破棄されます。パーティション関数で返されるピボット値が適切な場所にあるためです。

于 2015-09-22T22:58:05.963 に答える