バタフライネットワークによる確率的な選択ネットワーク

書誌事項

タイトル別名
  • A PROBABILISTIC SELECTION NETWORK WITH BUTTERFLY NETWORKS

この論文をさがす

説明

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

収録刊行物

詳細情報 詳細情報について

  • CRID
    1574231876908185472
  • NII論文ID
    110002812073
  • NII書誌ID
    AN1009593X
  • ISSN
    09196072
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ