間隔の決め方とは? わかりやすく解説

間隔の決め方

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/08/06 14:29 UTC 版)

シェルソート」の記事における「間隔の決め方」の解説

シェルソート実行時間時間計算量)は、比較時に選ぶ間隔hによって大きく異なる。前節の例ではhを2の累乗としたが、この場合最悪計算量が O ( n 2 ) {\displaystyle \mathrm {O} (n^{2})} となってしまう。各周回で同じ位置要素ばかりが比較交換されるため、h=1となった段階で「全体大まかに整列されている」という仮定成り立たなくなるためである。より効率良い計算量少ない)ソートを行うために、様々な間隔提案されてきた。以下の表は、間隔決定するための数列の例である。( n {\displaystyle n} は要素数) 数列一般項 (k ≥ 1)実際数列最悪計算時間備考n 2 k ⌋ {\displaystyle \left\lfloor {\frac {n}{2^{k}}}\right\rfloor } ⌊ n 2 ⌋ , ⌊ n 4 ⌋ , … , 1 {\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor ,\left\lfloor {\frac {n}{4}}\right\rfloor ,\ldots ,1} O ( n 2 ) {\displaystyle \mathrm {O} (n^{2})} ドナルド・シェル最初に考案した数列。 n {\displaystyle n} が2の累乗の時、上記動作例と同一3 k1 2 {\displaystyle {\frac {3^{k}-1}{2}}} ( ⌈ n 3 ⌉ {\displaystyle \left\lceil {\frac {n}{3}}\right\rceil } 以下) 1 , 4 , 13 , 40 , 121 , … {\displaystyle 1,4,13,40,121,\ldots } O ( n 3 2 ) = O ( n 1.5 ) {\displaystyle \mathrm {O} \left(n^{\frac {3}{2}}\right){=}\mathrm {O} (n^{1.5})} ドナルド・クヌース、 1973Pratt, 1971に基づく。平均計算時間は O ( n 1.25 ) {\displaystyle \mathrm {O} (n^{1.25})} 。 A 0 = 1 , A k = 4 k + 3 ⋅ 2 k1 + 1 {\displaystyle A_{0}{=}1,A_{k}{=}4^{k}+3\cdot 2^{k-1}+1} 1 , 8 , 23 , 77 , 281 , … {\displaystyle 1,8,23,77,281,\ldots } O ( n 4 3 ) = O ( n 1.33 … ) {\displaystyle \mathrm {O} \left(n^{\frac {4}{3}}\right){=}\mathrm {O} (n^{1.33\ldots })} Sedgewick, 1982 2 p 3 q {\displaystyle 2^{p}3^{q}} ( p ≥ 0 , q ≥ 0 {\displaystyle p\geq 0,q\geq 0} ) 1 , 2 , 3 , 4 , 6 , 8 , 9 , 12 , … {\displaystyle 1,2,3,4,6,8,9,12,\ldots } O ( n log 2 ⁡ n ) {\displaystyle \mathrm {O} \left(n\log ^{2}n\right)} Pratt, 1971既知数列最悪計算時間最小となるもの。間隔狭め方が細かすぎるため、実用性は低い。 これらの数列ソート間隔として利用する際は、(要素以内で)大きな数字から狭めていく。 3 k1 2 {\displaystyle {\frac {3^{k}-1}{2}}} を使う場合間隔hを1214013→4→1とする(hを3で整数除算していけばよい)。様々な間隔計算量について理論的に考察されているが、現状どのような間隔最適か(例えば、平均 O ( n log ⁡ n ) {\displaystyle \mathrm {O} (n\log n)} 時間となる数列があるか)は未解決問題である。

※この「間隔の決め方」の解説は、「シェルソート」の解説の一部です。
「間隔の決め方」を含む「シェルソート」の記事については、「シェルソート」の概要を参照ください。

ウィキペディア小見出し辞書の「間隔の決め方」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「間隔の決め方」の関連用語

間隔の決め方のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



間隔の決め方のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaのシェルソート (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS