数组理论基础

一句话概括 数组是存放在一段连续内存空间中的同类型数据集合，因此支持按下标 $O(1)$ 随机访问，但在中间插入或删除时通常需要移动后续元素，时间复杂度为 $O(n)$。

1 简易回答

数组有三个核心特点：

1. 元素类型相同。
2. 内存空间连续。
3. 可以通过从 0 开始的下标直接访问元素。

连续内存让数组可以根据"首地址 + 偏移量"直接定位元素，所以随机访问是 $O(1)$；代价是中间插入或删除会破坏原有顺序，需要移动其他元素，通常是 $O(n)$。

2 详细回答

2.1 1. 数组如何存储

假设有一个 int 数组：

1

int nums[5] = {10, 20, 30, 40, 50};

它在内存中可以理解为：

1
2
3
4
5

下标：   0      1      2      3      4
      ┌─────┬─────┬─────┬─────┬─────┐
元素：│  10 │  20 │  30 │  40 │  50 │
      └─────┴─────┴─────┴─────┴─────┘
地址： 1000   1004   1008   1012   1016

如果一个 int 占 4 字节，那么：

$$ \text{nums}[i]\text{ 的地址}=\text{首地址}+i\times 4 $$

更一般地：

$$ \operatorname{addr}(a[i])=\operatorname{base}(a)+i\times \operatorname{sizeof}(T) $$

这就是数组能够通过下标在 $O(1)$ 时间内访问任意元素的原因。

2.2 2. 为什么下标从 0 开始

下标可以看成元素相对首地址的偏移量：

• a[0]：从首地址偏移 0 个元素。
• a[1]：从首地址偏移 1 个元素。
• a[i]：从首地址偏移 $i$ 个元素。

因此从 0 开始可以直接使用 base + i × sizeof(T) 计算地址。

2.3 3. 插入和删除为什么慢

假设要删除下标 2 的元素，并保持其他元素的相对顺序：

1
2
3

删除前：10  20  30  40  50
删除后：10  20  40  50
                 ←   ←

原来位于后面的 40、50 都要向前移动。因此：

• 访问指定下标：$O(1)$
• 修改指定下标：$O(1)$
• 尾部插入：固定数组视实现而定；vector 通常均摊 $O(1)$
• 中间插入或删除：$O(n)$
• 按值查找（无序数组）：$O(n)$

“数组不能删除元素"怎么理解 固定长度数组的内存块和长度不会因为一次删除操作自动缩短。所谓"删除”，一般是覆盖目标元素、移动后续元素，再用一个逻辑长度表示有效范围。vector::erase 能提供删除接口，但底层仍需要移动元素。

2.4 4. C++ 中的数组与 vector

vector 是一个动态顺序容器，底层使用连续内存管理元素。扩容时通常需要申请新空间并移动或复制旧元素，相关迭代器、指针和引用可能失效。详见 vector深度解析。

2.5 5. 二维数组的内存布局

2.5.1 C++ 原生二维数组

1
2
3
4

int matrix[2][3] = {
    {0, 1, 2},
    {3, 4, 5}
};

C++ 原生二维数组按行连续存储，可以把它理解为：

1
2
3

matrix[0][0] → matrix[0][1] → matrix[0][2]
                                      ↓
matrix[1][0] → matrix[1][1] → matrix[1][2]

对一个有 cols 列的二维数组，行优先布局下：

$$ \operatorname{addr}(a[i][j]) =\operatorname{base}(a)+(i\times cols+j)\times \operatorname{sizeof}(T) $$

2.5.2 Java 二维数组

Java 的 int[][] 本质上是"数组的数组"：外层数组保存对各行数组的引用，各行可以分别创建，长度也可以不同。

1
2
3
4
5

int[][] matrix = {
    {1, 2, 3},
    {4, 5},
    {6, 7, 8, 9}
};

因此不能假设不同行在内存中彼此连续；而且 Java 不向程序员暴露可直接运算的真实内存地址。

3 知识扩展

3.1 1. 连续内存为什么通常更快

数组元素相邻，CPU 读取一个元素时通常会把附近的一块数据一起加载到缓存中。顺序遍历数组时，后续数据很可能已经在缓存里，因此具有较好的缓存局部性。

3.2 2. 数组与链表的核心取舍

3.3 3. 越界访问

C++ 原生数组和 vector::operator[] 不会自动检查越界。越界访问属于未定义行为，可能读到错误数据，也可能导致程序崩溃。调试时可使用 vector::at() 获得边界检查。

3.4 易错点

• 把 vector 直接等同于原生数组：二者都使用连续内存，但抽象层级和能力不同。
• 认为数组中间删除是 $O(1)$：定位可以是 $O(1)$，移动元素仍是 $O(n)$。
• 认为所有语言的二维数组布局都一样：C++ 原生二维数组与 Java 的数组嵌套模型不同。
• 忘记下标范围是 [0, size - 1]。
• 混淆"物理长度"和"逻辑长度"。

3.5 自测

1. 为什么数组可以在 $O(1)$ 时间内访问第 $i$ 个元素？
2. 删除数组中间的元素为什么通常是 $O(n)$？
3. C++ 原生二维数组和 Java int[][] 的内存模型有什么区别？
4. vector 扩容后，旧指针、引用和迭代器为什么可能失效？
5. 连续内存除了支持随机访问，还带来了什么性能优势？

3.6 我的补充

用自己的话重写 注意，某些列优先（Column-Major，如 Fortran）语言和 C++ 相反，先存完一列再存下一列，顺序是： [0][0]→[1][0]→[0][1]→[1][1]→[0][2]→[1][2] C/C++/Python 都是行优先，只有少数科学计算语言用列优先。

3.7 相关笔记

• 二分查找模板
• 链表常用操作总结