« CRF++ 0.46 | メイン | chasen.org 復活 »
2007年02月19日
動的配列への追加コストはなぜ O(1)?
動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが，どうしてかと言われると意外と難しいものです． というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです．実装を知っていないと答えられません．一般論として，1つ要素を追加するとき，配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります．コピーのコストは O(n) だから，追加コストも O(n) になるという議論が混乱の元になっています． こういうときは，要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです．一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです．
さて，std::vector や perl の配列といったほとんどの動的配列は，足りなくなったら配列を2倍にしていくという 実装が使われています．このアルゴリズムの「ならし解析」をやってみます.
追加を n 回繰り返したとき，配列を倍々にしていくので，コピー(再配置)が起きる回数は log n 回です． 各再配置で 1, 2, 4, 8 .. と要素をコピーするので，全体の総和は
1 + 2 + 4 + 8 + ... 2^(log n) = 2^(log n + 1) - 1 =~ 2n となります．
コピーが発生しない場合の数は n - log(n) =~ n 回です．(log n は無視できる) .
二つを合計すれば，高々 3n の要素がコピーされることになります．これを n で割った値が １つの要素を追加するときの平均的な計算量なので，結果として O(1) が導かれます．一般的に配列サイズを指数的に増やしていけば O(1) になります．
動的配列の実装方法は倍々以外にも考えられます．たとえば，固定長 k だけ逐次増やしていく実装の「ならし解析」はどうなるでしょうか．
再配置が行われる回数: n/k
コピーの要素の数: k + 2k + 3k + ... + n/k * k = k * (1 + 2 + ... + n/k) = k * n/k (1 + n/k) =~ (n^2)/k
1要素の平均計算量: O((n^2)/k) = O(n/k)
なんと! 固定長で増やしていく実装だと，O(n) になってしまいます．
動的配列の要素追加コストが O(1) になるといのは，倍々にしていくという内部の実装があってはじめて言えることです. 逆に言えば，倍々にする理由付けもこの議論から行えます．
投稿者 taku : 2007年02月19日 00:21
トラックバック
このエントリーのトラックバックURL:
http://chasen.org/~taku/blog/mt-tb.cgi/222
このリストは、次のエントリーを参照しています: 動的配列への追加コストはなぜ O(1)?:
» 高三で友達100人 from 乳首の取れた14歳-------s;0o
友達と恋人の違い（ヤルかどうか）について最近悩んでいます。もしよければ私のブログも見て頂けると嬉しいです。 [続きを読む]
トラックバック時刻: 2007年02月19日 09:38
» cialis from cialis
very nice site! [続きを読む]
トラックバック時刻: 2007年03月14日 17:35
» viagra from viagra
nice choice of colors. [続きを読む]
トラックバック時刻: 2007年03月14日 19:07