数组基础：底层原理篇
侧重：静态数组的内存模型、地址计算原理、O(1) 随机访问的本质
核心原理：静态数组的本质
1. 内存模型
静态数组在内存中的本质是一段连续的内存空间，以 int arr[10] 为例：
- 开辟连续空间：操作系统分配
10 * sizeof(int) = 40字节的连续内存 - 数组指针：
arr是指向这段内存首地址的指针 - 元素定位：每个元素占用固定大小（int = 4字节），通过首地址 + 偏移量精确定位
内存布局示意：
首地址 → [int][int][int][int][int][int][int][int][int][int]
↑ 0 1 2 3 4 5 6 7 8 9 (索引)
2. 地址计算原理（为什么索引从0开始？）
arr[i] 的本质计算：
目标地址 = arr首地址 + i * sizeof(元素类型)
arr[0]：首地址 + 0 = 首地址（第一个元素）arr[1]：首地址 + 1 * 4字节 = 第二个元素的首地址arr[2]：首地址 + 2 * 4字节 = 第三个元素的首地址
索引从0开始的原因：为了让 arr[0] 的计算不需要额外加法（偏移量为0），这是计算机寻址的自然表达。
3. O(1) 随机访问的本质
为什么数组可以 O(1) 访问任意索引的元素？
- 已知首地址（数组名
arr就是首地址） - 已知每个元素的大小（
sizeof(int) = 4字节） - 内存连续 → 地址计算只需一次乘法和一次加法
- 计算机内存寻址本身就是 O(1) 操作
访问 arr[i] 的步骤：
1. 计算偏移量：offset = i * sizeof(int)
2. 计算目标地址：target_addr = arr + offset
3. 从 target_addr 读取 4 个字节 → 得到元素值
这就是数组的超能力：随机访问。
4. 连续内存的代价
优势即劣势：连续内存给了 O(1) 访问能力，但也带来了限制：
| 操作 | 时间复杂度 | 原因 |
|---|---|---|
| 查/改（给定索引） | O(1) | 地址计算 + 内存寻址 |
| 末尾追加 | O(1) | 直接索引赋值 |
| 中间插入 | O(N) | 需要数据搬移，给新元素腾位置 |
| 中间删除 | O(N) | 需要数据搬移，保持连续性 |
| 扩容 | O(N) | 重新分配大块内存 + 复制所有数据 |
为什么不能就地扩展？
连续内存必须一次性分配。如果 int arr[10] 后面想加4字节，但后面的内存可能已被其他程序占用，无法保证连续性。只能重新申请更大的连续空间（如 int newArr[20]），再复制数据。
5. 动态数组的真相
动态数组 ≠ 解决静态数组的缺陷
动态数组（如 Java 的 ArrayList、C++ 的 std::vector）底层仍然是静态数组，只是封装了：
- 自动扩缩容逻辑（当空间不足时，申请新数组 + 复制）
- 增删查改的 API（让使用更方便）
时间复杂度与静态数组完全一致，只是把手动操作自动化了。
相关概念
- 时间复杂度：均摊时间复杂度概念
相关实体
- labuladong：算法学习平台作者
原理总结
数组的核心在于连续内存 + 固定元素大小，这让地址计算成为简单的算术问题，从而实现 O(1) 随机访问。但连续性的代价是增删操作需要数据搬移，这是无法避免的 trade-off。