kono@ie.u-ryukyu.ac.jp (Shinji KONO) writes:

> > しかしですね。以下の条件が満たされるならオーダーは変わんないですよ。
> > ・割り付けた領域には、少なくとも一回データが書き込まれる(初期化でも可)
> > ・ヒープサイズは生きているデータの量に比例して増加させてよい
> > ・GCのルート集合の大きさは、高々生きているデータの量に比例する程度
> 
> 2番目はちょっとずるいような気もするけど、その仮定だとO(N)に
> なる気がする。ってことは、メモリが足りなくなるような状況でな
> ければ、定数オーダの差しかないってことなのかな。

生きているデータの何倍も取るというわけではないです。

ふつうは生きているデータ量の50%くらい空きがあれば(つまりメモリ量は1.5 
倍)だいたいOKかと。

まあ、どんなメモリ管理をしても、少しは余裕が必要ですから。ずるいと言う
ほどでもないかと。

> なんか、まずい場合があったような気がするんだけど、いまいち、
> 思い付かないなぁ。ってことは、そういうことなんだろうか?
> 
> んーと、append の場合も時間計算量はおんなじなんだけど、破壊
> と非破壊だと、領域計算量が違いますよね。今の計算機は結構メモ
> リスピードネックだったりするので、O(N^2)とかの計算だとゴミが
> たくさんでないようにしないとまずいってのは、あるかな。

木構造だと破壊でも非破壊でも大差ないと思いますが、グラフを表現するには
破壊的書き換えを使うことが多いかも。で、本来グラフが必要なところを木だ
けでやろうとすると、領域計算量が指数関数で増えたりとか。

                                前田敦司