バタフライネットワークによる確率的な選択ネットワーク
スポンサーリンク
概要
- 論文の詳細を見る
選択・整列ネットワークの分野では,これまでに大きさO(nlogn)・段数O(logn)のものが発表されている.しかし,それらは存在性のみを考慮したものばかりであり,比例定数がかなり大きかった.最近になって,実装の容易なバタフライネットワークを用いた段数7.44logn + O(loglogn)の確率的な整列ネットワーグが発表された.これは確率アルゴリズムの概念に添って構築されており,注目に値するものである.本研究はこの手法を選択ネットワークに適用し,大きさ0.5n logn + O(n^<0.822>logn)・段数5.62logn + O(loglogn)の確率的な選択ネットワークを構築する.
- 一般社団法人情報処理学会の論文
- 1993-05-28