最適なソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/06/01 06:18 UTC 版)
「ソーティングネットワーク」の記事における「最適なソート」の解説
AKSネットワーク（発見者のAjtai（en:Miklós Ajtai）、Komlós（en:János Komlós (mathematician)）、Szemerédi（en:Endre Szemerédi）にちなむ）というソーティングネットワークは、 n 個の入力に対して段数 O(log n) ・サイズ O(n log n) となる。これは漸近的に最適なアルゴリズム（英語: asymptotically optimal algorithm）である。また、このAKSネットワークを簡潔にしたものが後にPaterson（en:Mike Paterson）によって発表されている。AKSネットワークは重要な発見ではあるが、Big-O 記法に隠された巨大な定数があり、実用に供されることはほとんどない。この理由のひとつとしては、エキスパンダーグラフ（en:expander graph）の構成が挙げられる。小さな c に対してサイズ cn log n のソーティングネットワークを見つけるのは、依然として未解決問題のままである。 1個から8個までの入力に対しては最適なソーティングネットワークが知られており、それぞれ 0, 1, 3, 5, 9, 12, 16, 19 個のコンパレータを持つ (Knuth, 1997)。10個までの入力に対する最小の段数も知られており、それぞれ 0, 1, 3, 3, 5, 5, 6, 6, 7, 7 である。
※この「最適なソート」の解説は、「ソーティングネットワーク」の解説の一部です。
「最適なソート」を含む「ソーティングネットワーク」の記事については、「ソーティングネットワーク」の概要を参照ください。
- 最適なソートのページへのリンク
