河野真治 @ 琉球大学情報工学です。

In article <m3sma084lr.fsf@nospam.maedapc.cc.tsukuba.ac.jp>, MAEDA Atusi <maeda-news@ialab.is.tsukuba.ac.jp> writes
> しかしですね。以下の条件が満たされるならオーダーは変わんないですよ。
> ・割り付けた領域には、少なくとも一回データが書き込まれる(初期化でも可)
> ・ヒープサイズは生きているデータの量に比例して増加させてよい
> ・GCのルート集合の大きさは、高々生きているデータの量に比例する程度

2番目はちょっとずるいような気もするけど、その仮定だとO(N)に
なる気がする。ってことは、メモリが足りなくなるような状況でな
ければ、定数オーダの差しかないってことなのかな。

なんか、まずい場合があったような気がするんだけど、いまいち、
思い付かないなぁ。ってことは、そういうことなんだろうか?

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

---
Shinji KONO @ Information Engineering, University of the Ryukyus
河野真治 @ 琉球大学工学部情報工学科