1. Kyoto University Research Information Repository
  2. 400　数理解析研究所
  3. 1.講究録
  4. 2040 理論計算機科学の最先端
このアイテムのアクセス数: 102

    このアイテムの引用には次の識別子を使用してください: http://hdl.handle.net/2433/236904
このアイテムのファイル:
ファイル 記述 サイズフォーマット 
2040-05.pdf757.64 kBAdobe PDF見る/開く
完全メタデータレコード
DCフィールド値言語
dc.contributor.author照山, 順一ja
dc.contributor.author岩間, 一雄ja
dc.contributor.alternativeTeruyama, Junichien
dc.contributor.alternativeIwama, Kazuoen
dc.contributor.transcriptionテルヤマ, ジュンイチ-
dc.contributor.transcriptionイワマ, カズオ-
dc.date.accessioned2019-03-07T05:44:34Z-
dc.date.available2019-03-07T05:44:34Z-
dc.date.issued2017-07-
dc.identifier.issn1880-2818-
dc.identifier.urihttp://hdl.handle.net/2433/236904-
dc.description.abstract比較ソートにおける効率は主に比較回数によって計られる. 本研究では, できるだけ平均の比較回数が少ない比較ソートアルゴリズムの設計を目的とする. 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)が達成されることを示した.ja
dc.format.mimetypeapplication/pdf-
dc.language.isojpn-
dc.publisher京都大学数理解析研究所ja
dc.publisher.alternativeResearch Institute for Mathematical Sciences, Kyoto Universityen
dc.subject.ndc410-
dc.title整列問題の平均比較回数 (理論計算機科学の最先端)ja
dc.typedepartmental bulletin paper-
dc.type.niitypeDepartmental Bulletin Paper-
dc.identifier.ncidAN00061013-
dc.identifier.jtitle数理解析研究所講究録ja
dc.identifier.volume2040-
dc.identifier.spage35-
dc.identifier.epage42-
dc.textversionpublisher-
dc.sortkey05-
dc.address国立情報学研究所・JST, ERATO, 河原林巨大グラフプロジェクトja
dc.address京都大学数理解析研究所ja
dc.address.alternativeNational Institute for Informatics・JST, ERATO, Kawarabayashi Large Graph Projecten
dc.address.alternativeRIMS, Kyoto Universityen
dcterms.accessRightsopen access-
dc.identifier.jtitle-alternativeRIMS Kokyurokuen
出現コレクション:2040 理論計算機科学の最先端

アイテムの簡略レコードを表示する

Export to RefWorks


出力フォーマット 


このリポジトリに保管されているアイテムはすべて著作権により保護されています。