きまぐれ日記: 動的配列への追加コストはなぜ 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)と言うそうです． さて，s

[kateinoigaku]

あとで読む #iosdc #b

[massa142]

ならし解析

[zorio]

なるほど。納得。すっきり。

[Kureduki_Maari]

きまぐれ日記: 動的配列への追加コストはなぜ O(1)? -

[yaotti]

ならし解析，オーダーは平均で考える

[akhr2501]

動的配列のサイズ変更時のコストについて

[hitsujibane]

ならし解析について

[craf]

わかりやすい解説

[webmarksjp]

プログラミング

[ftnk]

> 一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです．

[hitobasiler]

『1 + 2 + 4 + 8 + ... 2^(log n) = 2^(log n + 1) - 1 =~ 2n』の導出と=~の意味が分からず断念

[nilab]

きまぐれ日記: 動的配列への追加コストはなぜ O(1)?

[ringo_]

narasi

[f99aq]

ならし解析

[nirvash]

実装によってコストは変わる。

[samejima]

足りなくなったら配列を2倍にする理由

[nitoyon]

足りなくなったら倍のメモリ確保する実装の理論的な裏づけ。

[agx]

メモリ確保を倍々にすることで、n回追加を繰り返したときの平均が１になる

[hiromark]

"動的配列の要素追加コストが O(1) になるといのは，倍々にしていくという内部の実装があってはじめて言えることです."、なるほど。いい勉強になりました。

[odz]

std::vector が倍々に領域拡張する理由