＜集大成＞アルゴリズム大辞典

＜集大成＞アルゴリズム大辞典 at TECH

392:デフォルトの名無しさん
08/05/10 20:20:42
>>391
「挿入ソート」にもマイナーバージョンがいくつもあるので，
もう少し詳しいアルゴリズムを述べてくれないと厳密には解析できない．

まあ大雑把には，挿入ソートは
・空リストから初めて，要素を一つづつ "INSERT" する
・INSERT は，ソート済みのリストに要素を順序を壊さないように追加する
というアルゴリズムなので，これを解析する．

計算量を要素の比較回数で評価することにする．
長さ m のリストに対して INSERT するときの比較の回数を T(m) と書くと，
全体での比較の回数は Σ[m=0..n-1] T(m) になる．

T(m) は実装にもよるが，順番に比較していって挿入できる場所を探すと
最大 m 回の比較が発生しうる．つまり T(m) ≦ m．
よって全体の比較回数は Σ[m=0,n-1] T(m) ≦ Σ[m=0,n-1] m = n(n-1)/2 = O(n^2)

多分上の説明だと分からないところがあると思うので，ここが分からんとか聞いとくれ．

次ページ

続きを表示

1を表示