ダウンロード数: 71
このアイテムのファイル:
| ファイル | 記述 | サイズ | フォーマット | |
|---|---|---|---|---|
| 2040-05.pdf | 757.64 kB | Adobe PDF | 見る/開く |
| タイトル: | 整列問題の平均比較回数 (理論計算機科学の最先端) |
| 著者: | 照山, 順一  岩間, 一雄 |
| 著者名の別形: | Teruyama, Junichi Iwama, Kazuo |
| 発行日: | Jul-2017 |
| 出版者: | 京都大学数理解析研究所 |
| 誌名: | 数理解析研究所講究録 |
| 巻: | 2040 |
| 開始ページ: | 35 |
| 終了ページ: | 42 |
| 抄録: | 比較ソートにおける効率は主に比較回数によって計られる. 本研究では, できるだけ平均の比較回数が少ない比較ソートアルゴリズムの設計を目的とする. EdelkampとWeiβによってFordとJohnsonのアルゴリズムの平均比較回数がnlgn-1.3999n+O(lgn)であることが示されている. また, 情報理論的下限から平均比較回数の下限はlceil lgn!rceil approx nlgn-1.4426n+O(lgn)であることが知られている. 本研究では, 2つの要素を挿入する操作を与えることにより, 平均比較回数が高々nlgn-1.4034+O(lgn)となるアルゴリズムを設計した. また, 我々のアルゴリズムとFordとJohnsonのアルゴリズムを組み合わせることにより, 平均比較回数nlgn-1.4106n+O(log n)が達成されることを示した. |
| URI: | http://hdl.handle.net/2433/236904 |
| 出現コレクション: | 2040 理論計算機科学の最先端 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。