2

たとえば、51 要素の中央値を抽出するには、51 を 25 の H(ead) グループに分割し、その後に中央値、25 の T(ail) が続きます。私が知っているすべてのアルゴリズムは、 H と T が [min(H), max(H)[ と ]min(T), max(T)] がオーバーラップしないような追加のプロパティ。

この追加のプロパティは必須であることが証明されていますか (私はそう思います)? どこで証拠を見つけることができますか（長い間行われていると思います）？

（これはアルゴリズムへの愛のためだけです）

4

1 に答える 1

0

要素が一意でない場合、実際には 2 つのセットが重複する可能性があります (51 個の同一要素のリストを想像してください...)。

要素が一意である場合、重複しないプロパティは矛盾によって簡単に証明できます。一意の要素の分割から、次のことがわかります。

  • x < H のすべての x の中央値
  • y > H のすべての y の中央値

H と T が重複しているとします。次に、次のようになります。

  • ある x=max(H), y=min(T) に対して x >= y

しかし、それは次のことを意味します。

  • x >= y > 中央値

x < 中央値を既に知っているため、これは矛盾です。したがって、2 つのセットが重複することはありません。

于 2014-01-01T20:43:28.187 に答える