什么是数组，以及其操作的时间复杂度是多少？

Question

Accepted Answer

**数组**是内存中的连续块，用于存储相同类型的元素，从 `0` 开始索引。由于元素彼此相邻，第 `i` 个元素的地址可直接计算为 `base + i * elementSize`，从而实现 **O(1) 随机访问**。

## Memory layout

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

## Example

```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
```

## Complexity

| Operation | Time |
|---|---|
| Access by index | O(1) |
| Search (unsorted) | O(n) |
| Append (dynamic) | O(1) amortized |
| Insert/delete at front/middle | O(n) |

## Trade-offs

- **Strengths:** 快速索引、高速缓存友好（数据连续）、内存开销低。
- **Weaknesses:** 在中间插入/删除为 O(n)；固定大小的数组需要复制才能扩展。

## 为什么这很重要

数组是大多数其他数据结构的基础——字符串、哈希表、堆和动态列表都是建立在数组之上的。

其缓存局部性通常使"较慢"的 Big-O 数组在实际基准测试中击败"更快"的基于指针的结构。

Operation	Time
Access by index	O(1)
Search (unsorted)	O(n)
Append (dynamic)	O(1) amortized
Insert/delete at front/middle	O(n)