文献

J-GLOBAL ID：201802287188024071   整理番号：18A0471365

シェルソートの平均的計算量について【Powered by NICT】

On the average-case complexity of Shellsort

著者 (2件)： Vitanyi Paul (CWI, Science Park 123, 1098XG, Amsterdam, The Netherlands) ,  Vitanyi Paul (University of Amsterdam, Dept Computer Science, Science Park 904, 1098XH, Amsterdam, The Netherlands)
資料名： Random Structures & Algorithms  (Random Structures & Algorithms)
巻： 52  号： 2  ページ： 354-363  発行年： 2018年 
JST資料番号： W0149A  ISSN： 1042-9832  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： シェルソートのインバージョンの数の平均的複雑さに関する増加配列で発現した下限を証明した。をチェックできるこの下限は全てのケースでシャープである。この下限の特殊なケースは,一般的なJiang Li Vitanyi下限が得られた。は,例えば,Yao Janson Knuth3パスで平均的複雑さを正確に決定する新しい結果を得た。Copyright 2018 Wiley Publishing Japan K.K. All Rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： CASE ,  *計算量
準シソーラス用語： 複雑性 , 【Automatic Indexing@JST】

著者キーワード (4件)： シェルソート ,  平均例計算量 ,  下限 ,  Kolmogorov複雑さ

分類 (3件)： 計算理論  (JB02000A) ,  数理地質学  (DE01020S) ,  地震探査  (DE10030B)

タイトルに関連する用語 (2件)： 平均 ,  計算量