ソートネットワークサイズ上下限の説明

Question

このウィキペディアの記事を参照してください：https://en.wikipedia.org/wiki/Sorting_network、段落に焦点を合わせてソートネットワークの構築。

Size, upper boundとSize, lower bound（表内）は何ですか？ lower boundは、n個の数字の入力を正しくソートするのに必要な最小限の接続を意味すると思います（私は正しいですか？）。もしそうなら、なぜupper boundで気になるのですか？理論的には、upper boundよりも多くの接続を使用することができますが、どうすればそれを確立できますか？ リンクされた論文も読んだことがありますが（参考文献11）、私はまだ混乱しています。

Answer 1

表後の段落は、結合した上限及び下部の意味についてヒントを与える：ソーティングネットワーク

最小1〜10個の入力、（すなわちサイズ最適）については知られており、ためのものですそれらのサイズの下限より高い値は、Van Voorhisによる補助定理を用いて誘導的に誘導することができる。S（n + 1）≧S（n）+ log2（n）÷。

テーブル内の«上限»は、明らかに現在の並べ替えする要素の一定数のを知られている最も大き最適なソートネットワークの大きさに対応します。 1〜10要素の既知のサイズ最適ソーティングネットワークが最適であることが証明されていますが、より多くの要素の既知のサイズ最適ソートネットワークが実際に最適なソートネットワークであるとは確信していません。 «下界»は、所与の数の要素をソートするソートネットワークの理論上の最小サイズに対応する。このサイズのソートネットワークは存在しない可能性があるが、まだ実証されていない。

まとめると：

• «上限»が発見されたほとんどのサイズに最適なソートのネットワークを表します。
• «下限»は、ネットワークの理論上の最小サイズを表します。このようなネットワークは存在しないことは証明されていませんが、このサイズの実行可能なネットワークも見つかりませんでした。サイドノートとして

---

Iは、サイズ最適ソーティングネットワークとa libraryを維持し、その大きさは（もthe documentationとthe implementationを参照）テーブルから«上限»に相当します。