位置を計算して取り出す
固定長要素を連続した領域に並べる配列では、要素iの位置は「先頭アドレス+i×要素の大きさ」で求められます。0番目から数え、各要素が4バイトなら、先頭から12バイト先にあるのは3番目の要素です。この直接計算が、通常のRAMモデルで添字参照をO(1)とする理由です。要素がオブジェクトへの参照なら連続するのは参照の領域であり、オブジェクト本体まで連続するとは限りません。
途中への挿入で何が動くか
配列[10,20,30,40]の添字1へ15を挿入すると、順序を保つには20、30、40を一つずつ後ろへ移します。空き領域があっても移動は必要です。長さnの配列で先頭付近への挿入や削除を行えば、移動数はnに比例します。対して、順序を保つ必要がない削除なら、最後の要素で穴を埋める設計も考えられます。操作の目的を明確にすると、同じ配列でも必要な処理が変わります。
動的配列の末尾追加
動的配列は長さと確保済み容量を分けて持ちます。容量4に4要素が入っているとき、5要素目の追加で容量8へ増やす方式なら、既存4要素を別の領域へ移します。この1回の追加はO(n)ですが、容量を一定倍率で増やす方式では、多数の追加を合計したコストから末尾追加を償却O(1)と評価できます。毎回ちょうど1要素分だけ拡張する方式に、この評価をそのまま当てはめることはできません。
選ぶときの確認点
配列は順次走査と添字参照に向いています。ただし、未整列の配列から値を探す処理は、位置が分からないので通常O(n)です。添字参照のO(1)と値検索のO(n)を混同しないようにします。実際の速度はキャッシュ、要素サイズ、再確保、言語の境界検査にも影響されます。頻繁な中間挿入があるなら、連結リストや木も候補にし、探索の頻度とメモリ使用量を含めて選びます。
| 操作 | 条件 | 時間 |
|---|---|---|
| 添字参照 | 添字が既知 | O(1) |
| 値検索 | 未整列 | O(n) |
| 中間挿入 | 順序を保つ | O(n) |
| 末尾追加 | 一定倍率の容量拡張 | 償却O(1) |