Dequesによる順列のソーティングについて
スポンサーリンク
概要
- 論文の詳細を見る
本論文では, 任意の順列をdequesの直列結合によってソートするために必要なdequesの個数について論じた. そしてひとつのdequeからの出力が, そのdequeへのすべての入力が完了してからでなければ行われない場合について, すべての順列がソートできるためには(log_2n)/2個のdequesが必要であり,「log_2n」個の制限つきdequesで十分であることを示した. なお上の条件のもとでは, dequesの直列列結合は2個のdequesの両方向結合によってシミュレートでき, 上記の個数はソートに要するパスの回数と解釈できる.
- 一般社団法人情報処理学会の論文
- 1980-01-15
著者
関連論文
- 多値論理 (<特集>非標準論理とその応用)
- 研究の環境 : 極限状況からのアプローチ(8.環境)(極限へのアプローチ)
- 4. 行列積の漸近的計算量 (アルゴリズムの最近の動向)
- 双端キューの並列結合によるソーティングについて
- 計算の複雑さについて
- 安全クイックソート
- Dequesによる順列のソーティングについて
- 多項式の前処理つき計算の複雑さについて
- 多値論理関数族の完全性--歴史と… (多値論理)
- 離散数学とはなにか (離散数学のすすめ--現代数学の新天地)
- アルゴリズムについて (アルゴリズムの発見)
- アルゴリズムとグラマ (生成発展系--アルゴリズムとグラマ)
- オ-トマトン系の完全性 (オ-トマトン構造)
- 言語と数学 (言語)
- 知識構造と数学 (知識構造)
- 論理素子集合の順序回路に基づく完全性