シェルソートの計算量を求める方法について

質問

シェルソートで最悪の場合の計算量を求めたいです。
オーダーがnの二乗になるは知っていますが、その求め方、式がしりたいです。
要素数をN、感覚を４、２、１でお願いします。

考え方として各間隔のときのソート結果を無視して、各間隔時に単純挿入ソートと同様にして計算するのでしょうか？
それとも、各間隔でのソート結果を考慮するべきなのでしょうか？

できれば計算式と考え方、両方教えていただければありがたいです。

回答よろしくお願いします。

回答No.1

masa2211

>要素数をN、間隔を４、２、１でお願いします。
間隔逆順を、1,2,4,8,16....ｍ、2ｍ....
という数列、の意味にとります。
初期数列が　1,2,1,2、......
は、間隔が粗い間は全く整列されず、間隔１で初めて交換が発生し、
間隔１の時だけ考えて、ａ番目のデータは、a/2個まで順次比較される、というのがN回繰り返されるから
N^2であることが確定。

なお、効率が悪い間隔をわざわざ用いるのか不明。
逆順で、
1,2,3,7,15.....m,2m-1か
1,4,13,40....m,3m+1
のように、間隔がバラバラであれば、最悪でｎ(logN)^2で整列できたんじゃなかった？
　※データ数があまりにも小さい場合（たとえば、後者の間隔を使ってN=3の場合）はN＾2ですが、
　　それは無しとし、充分にNが大きいとして。