3

分割されたセット S の要素数が k 番目に小さい数とどのように関係しているかを理解するのに苦労しています。次の疑似コードがあるとします。

 Select (k,S)
  if |S|=1 then return a in S
  Choose random a in S
  Let S1,S2,S3 be sets of elements in S (<,=,> to a)
  If |S1|>=k then return Select(k,S1)
  Else if |S1| + |S2| >= k then return a
  Else return Select(k-|S1|-|S2|, S3)

私が知っていることから、k 番目に小さい要素を見つけるために、ピボットを選択し、ピボットの周りの数字を並べ替え、小さい数字はすべて左に、大きい数字はすべてピボットの右に配置します。次に、k 番目に小さい数を見つけたい場合は、それをピボットの位置と比較します。ピボットの位置が k より大きい場合は、ピボットの左側を調べ、ピボットの位置が k より小さい場合は、 、私は右に見て、そこから再帰します。

しかし、上記の疑似コードでは、上記のピボットと k の比較がどこで行われているのかわかりません。つまり、|S1| ではなく a >= k と比較すべきではないでしょうか。>= k、a がピボットなので?

この k との比較では、セット内の要素の数はどのように作用するのでしょうか?

4

1 に答える 1

1

S1 は a より小さい数の集合です。S2 は数 == a の集合です。S3 は数 >= a の集合です。これにはすでに多くの比較が含まれています。

|S1|の場合 >= k の場合、a より小さい数のセットは k 要素を超えます。したがって、k 個の最小数は既に S1 に含まれています。

そうでない場合は、S1 に含まれていないため、S2 または S3 に含まれている必要があります。

|S1|+|S2|の場合 >= k の場合、もちろん S1 または S2 にある必要があります。これは S1 にないため、S2 にある必要があります。S2 = {a} なので、k の最小数は a です。

これに当てはまらない場合は、S3 にある必要があります。したがって、検索は S3 に制限できます。S1 と S2 に含まれる数値は S3 から欠落しており、S3 のすべての数値よりも小さいため、これは k-|S1|-|S2| を検索する必要があることを意味します。S3 の最小数。

于 2013-07-21T10:47:58.110 に答える