配列とは何か、またその操作の計算量は何か？

Question

Accepted Answer

**配列**は同じ型の要素を保持するメモリの連続ブロックで、`0`からインデックスされます。要素が隣同士に配置されているため、要素`i`のアドレスは`base + i * elementSize`として直接計算され、**O(1)の直接アクセス**が可能です。

## メモリレイアウト

```text
index:    0     1     2     3     4
        +-----+-----+-----+-----+-----+
arr =   | 10  | 20  | 30  | 40  | 50  |
        +-----+-----+-----+-----+-----+
address: base  +4    +8    +12   +16   (4-byte ints)
```

## 例

```python
arr = [10, 20, 30, 40, 50]
x = arr[3]            # O(1) — direct index math
arr.append(60)        # amortized O(1) (dynamic array)
arr.insert(0, 5)      # O(n) — shift every element right
arr.pop(0)            # O(n) — shift every element left
```

## 計算量

| 操作 | 時間計算量 |
|---|---|
| インデックスによるアクセス | O(1) |
| 検索（未ソート） | O(n) |
| 追加（動的） | O(1) 償却 |
| 中間への挿入/削除 | O(n) |

## トレードオフ

- **利点：** 高速なインデックスアクセス、キャッシュ効率がよい（データが連続）、メモリオーバーヘッドが低い。
- **欠点：** 中間への挿入/削除がO(n)；固定サイズの配列は拡張時にコピーが必要。

## なぜ重要なのか

配列はほとんどの他のデータ構造の基礎となります — 文字列、ハッシュテーブル、ヒープ、動的リストはすべて配列の上に構築されています。

それらのキャッシュ局所性により、「遅い」Big-O計算量の配列が「高速」なポインタベースの構造を実ベンチマークで上回ることがよくあります。

操作	時間計算量
インデックスによるアクセス	O(1)
検索（未ソート）	O(n)
追加（動的）	O(1) 償却
中間への挿入/削除	O(n)