数组与动态数组：下标从 0 开始的原因

前置知识#

• 已完成 算法分析基础：会用大 O 描述代价、会算空间这本账、会用 timeit 验证。

学习目标#

读完本文你将能够：

1. 用寻址公式解释数组随机访问 O(1) 与「下标从 0 开始」的原因；
2. 用实验证明数组中间插入/删除是 O(n)；
3. 解释动态数组扩容的倍增策略与均摊 O(1) 的含义，并实测 Python list 的容量增长；
4. 说出缓存局部性给连续内存带来的第二重红利，并实测链式结构的真实代价；
5. 认识双指针/滑动窗口/前缀和三个数组技巧的适用信号，并能独立写出前缀和与原地双指针的参考实现。

预计 60 到 90 分钟。

1. 你现在要解决什么问题#

「数组的下标为什么从 0 开始」是每个程序员的第一次哲学追问，答案藏在内存的物理现实里：数组是一段连续的、等大小的格子。访问第 i 个元素不需要数格子——一个乘法一个加法直接算出地址。理解这个物理模型，数组的一切性能特征都会变成「显然」。

2. 最小可运行实验：寻址公式与 O(1)#

import timeit

arr = list(range(1000000))          # 一百万个连续整数

# 访问首元素与末元素——理论上耗时相同
t_first = timeit.timeit(lambda: arr[0], number=1000000)
t_last  = timeit.timeit(lambda: arr[999999], number=1000000)
print(f"arr[0]      : {t_first:.3f}s / 百万次")
print(f"arr[999999] : {t_last:.3f}s / 百万次")

预期输出（数值因机器而异，两条几乎相等）：

arr[0]      : 0.021s / 百万次
arr[999999] : 0.022s / 百万次

寻址公式：arr[i] 的地址 = 数组首地址 + i × 单元素大小。一次乘法一次加法，与 i 是 0 还是 999999 无关——这就是随机访问 O(1)，也是「下标从 0 开始」的原因：第 i 个元素的偏移量恰是 i × 大小，从 0 数起公式才干净。

3. 发生了什么：连续是把双刃剑#

连续内存买来 O(1) 随机访问，卖掉两样东西：

插入/删除要搬家。在开头插入一个元素，后面一百万个全部右移一格：

import timeit
arr = list(range(1000000))
t_head = timeit.timeit(lambda: arr.insert(0, -1), number=1000)
t_tail = timeit.timeit(lambda: arr.append(-1), number=1000)
print(f"头部插入 x1000: {t_head:.3f}s")   # 明显更慢：每次搬 100 万个
print(f"尾部插入 x1000: {t_tail:.3f}s")   # 几乎免费

预期输出趋势（数值因机器而异）：

头部插入 x1000: 2.914s
尾部插入 x1000: 0.058s

头部插入是 O(n)、尾部追加均摊 O(1)——同一个结构，操作位置不同，代价差五个数量级。

4. 核心概念一：动态数组的倍增扩容#

Python 的 list、Java 的 ArrayList、C++ 的 vector 本质都是「动态数组」：内部预分配一块空间，满了就申请一块约 1.5 到 2 倍大的新内存，整体搬家。单次扩容是 O(n)，但按倍增策略，n 次追加的总搬移次数是 n 的常数倍——均摊 O(1)：偶尔贵一次，平均每次很便宜。

亲手看 Python list 的扩容（sys.getsizeof 返回对象占用字节数）：

import sys
a = []
sizes = []
for i in range(100000):
    a.append(i)
    sizes.append(sys.getsizeof(a))
print(sizes[0], sizes[999], sizes[9999], sizes[99999])

预期输出（CPython 的具体序列因版本而异）：

56 9040 87616 857184

读法：容量不是每次 +1，而是阶梯式跳涨——「容量快满 → 搬进更大的家」。把 sizes 画成折线，倍增的楼梯清晰可见。均摊 O(1) 的直觉：搬 10 次家摊到 100000 次入住，平均每次近乎免费。

5. 核心概念二：连续内存的第二重红利——缓存局部性#

寻址公式只解释了 O(1)，连续内存还有一层寻址公式里看不到的红利：CPU 不按单个字节读内存，而按整块「缓存行」读（典型 64 字节）。访问 arr[i] 时，arr[i] 周围的邻居已经被一并搬进高速缓存——顺序扫一遍数组，几乎每一笔数据都是缓存命中的「顺路取货」。链表则相反：节点散落在堆的各处，每跳一个 next 指针都可能是一次缓存未命中，等于「每件货都跑一趟仓库」。

用「数组 vs 链式结构」的对照实验量一量这笔红利（链式结构用 [值, 下一节点] 模拟，200000 个节点串成链）：

import timeit, sys

N = 200000
arr = list(range(N))               # 连续存储：一段整块内存

head = None                        # 链式存储：节点散落，靠引用相连
for v in reversed(range(N)):
    head = [v, head]

def sum_array():
    s = 0
    for x in arr:
        s += x
    return s

def sum_linked():
    s = 0
    node = head
    while node is not None:
        s += node[0]
        node = node[1]             # 每步一次指针跳转
    return s

assert sum_array() == sum_linked()
print("数组  x50: %.4fs" % timeit.timeit(sum_array, number=50))
print("链表  x50: %.4fs" % timeit.timeit(sum_linked, number=50))
print("list 本体:", sys.getsizeof(arr), "bytes")
print("链节点本体:", sys.getsizeof([0, None]) * N, "bytes")

实测（数值因机器而异，倍数关系稳定）：

数组  x50: 0.2528s
链表  x50: 0.3936s        （顺序求和慢约 1.6 倍）
list 本体: 1600056 bytes
链节点本体: 14400000 bytes （是 list 本体的 9 倍，还没算每个整数对象自身）

诚实地解读三件事：

1. 空间差距是铁打的：同样的 20 万个数，链式结构仅对象本体就是数组的 9 倍——每个节点要多存一个引用，且零散小对象有分配开销。这正是 010 篇「空间这本账」的实物案例；
2. 速度差距在解释器语言里被稀释：Python 每步都有字节码与对象模型的固定开销，1.6 倍里缓存未命中只占一部分。同样的实验在 C/Rust 这类编译语言里，缓存效应会被放大到数倍以上——硬件机制相同，解释器开销掩盖了多少倍数，取决于语言；
3. 方向永远一致：顺序访问连续内存不慢于跳着访问零散内存。这个不等式不需要实验背书，它是缓存行机制的直接推论——这也是为什么 090 篇讲堆排序时，会提它跳跃访问导致实际比快排慢。

6. 核心概念三：数组三技巧的适用信号#

数组是最考验「识别信号」的结构，三个高频技巧先认识名字：

• 双指针：有序数组里找「两数之和」，一头一尾相向而行——把 O(n²) 降到 O(n)；
• 滑动窗口：「最长不含重复字符的子串」，窗口右扩左收，每个元素只进出一遍；
• 前缀和：「任意区间求和」被大量查询时，先算一遍累积和，区间和变成两次减法。

它们共同的底层依据都是「数组支持 O(1) 随机访问」——没有这条，一切技巧无从谈起。完整专题在刷题手册篇展开（参考层），这里把前缀和完整走一遍，因为它是三个技巧里最适合体会「预处理换查询」思想的：

场景：数组 nums 长 n，随后有 q 次「求区间 [l, r] 的和」。朴素做法每次查询扫一遍区间，最坏 O(n)×q；前缀和先花 O(n) 建一张累积和表，之后每次查询 O(1)：

nums = [3, 1, 4, 1, 5, 9, 2, 6]

# 第一步：建前缀和。prefix[i] = 前 i 个元素的和（prefix[0] 留 0 作哨兵）
prefix = [0]
for x in nums:
    prefix.append(prefix[-1] + x)
# prefix = [0, 3, 4, 8, 9, 14, 23, 25, 31]

# 第二步：区间 [l, r]（0 起、含两端）的和 = prefix[r+1] - prefix[l]
def range_sum(l, r):
    return prefix[r + 1] - prefix[l]

print(range_sum(1, 4))   # 1+4+1+5 = 11
print(range_sum(0, 7))   # 全表和 = 31

为什么 prefix[r+1] - prefix[l] 成立：prefix[r+1] 是「前 r+1 个」的和，减掉「前 l 个」的，剩下的恰好是第 l 到第 r 个。prefix[0] = 0 这个哨兵让 l=0 的查询不需要特判——加一个哨兵消灭一个 if，是数组类技巧的通用手法（090 篇的堆、190 篇的线段树都会再见）。

7. 修改实验#

1. 用 arr.insert(len(arr)//2, -1)（中部插入）× 1000 计时，确认代价介于头尾之间且随数组增长而变差；
2. 对比 arr.pop(0)（头部弹出，O(n)）与 collections.deque 的 popleft()（O(1)）各 10 万次——这就是队列应该用什么实现的答案；
3. 把 range(1000000) 换成 range(500000) 再测扩容序列，验证「阶梯形状相同、绝对值减半」；
4. 把第 5 节实验的 N 从 200000 改成 50000 与 800000 各跑一次，确认链表慢的倍数大致稳定——「缓存红利不随规模消失，只被解释器开销稀释」；
5. 给前缀和加一个能力：range_update 的反面需求「单点改值后大量区间查询」，手动改 nums[3] = 100 后直接查 range_sum(0, 7)，观察结果错在哪——体会前缀和「读多写少才划算」的边界，写多读少正是 190 篇线段树的入场券。

8. 小练习#

预测题（先写答案再验证）：对含 100 万元素的 list，以下操作各是什么复杂度？

arr[500000]            # 操作 A
arr.insert(999999, 1)  # 操作 B（尾部前一位）
arr.index(42)          # 操作 C（42 在数组里吗？在的话在最前）

修改题：把「删除列表中所有 0」的朴素写法（边遍历边 remove，O(n²) 且有跳项陷阱）改为一次遍历的 O(n) 写法（构建新列表），用 10 万元素实测对比。

修 Bug 题：同事在循环里反复 arr.insert(0, x) 收集「倒序日志」，百万条时卡死。指出复杂度问题并给出 O(n) 的替代（append 后反转），实测验证。

挑战题（不看提示）：只用「下标读写 + 长度」实现原地反转数组（首尾双指针交换），要求 O(n) 时间 O(1) 额外空间；用 100 万元素实测并与 arr[::-1]（Python 切片）耗时对比，解释切片为什么也不慢。

9. 动手实践：遮代码自检#

先只读任务与提示，自己写完再看参考实现。

任务：写 build_prefix(nums) 返回前缀和列表，写 range_sum(prefix, l, r) 查询闭区间和；然后用它解这道变体题：count_range(nums, a, b) 返回「值在 [a, b] 之间的元素个数」，要求预处理 O(n log n)、单次查询 O(log n)。

提示：先把数组排序（排序后「值在区间内」变成「下标在区间内」，就落回前缀和/二分的舒适区）；查「小于等于 x 的个数」用二分插入点（170 篇的 bisect_right 思想，这里手写）；区间个数 = 右端点个数 − 左端点个数。

参考实现（先自己写完再往下看）：

def count_range(nums, a, b):
    nums = sorted(nums)                  # 预处理 O(n log n)
    def leq(x):                          # <= x 的元素个数（手写 bisect_right）
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] <= x: lo = mid + 1
            else: hi = mid
        return lo
    return leq(b) - leq(a - 1)           # 区间计数 = 前缀相减，同前缀和一脉相承

print(count_range([3, 1, 4, 1, 5, 9, 2, 6], 2, 5))   # 4（即 3,4,5,2）
# 自检：a-1 处理「a 本身也算」的边界；若用 leq(b) - leq(a) 就漏掉了等于 a 的元素

任务：实现原地版「两数之和 II」（有序数组找两数使其和为 target，返回下标对）：先写暴力双循环 O(n²) 验证正确性，再改成首尾双指针 O(n)，两者在 [2, 7, 11, 15], target=9 与随机大数组上对拍。

提示：左指针指最小、右指针指最大；和偏小 只有左移左指针能变大，和偏大 只有左移右指针能变小——每一步至少淘汰一个下标，所以是 O(n)。双指针不写新数组，空间 O(1)。

参考实现（先自己写完再往下看）：

def two_sum_sorted(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target: return [lo, hi]
        if s < target:  lo += 1   # 只能靠左值变大
        else:           hi -= 1   # 只能靠右值变小
    return None

print(two_sum_sorted([2, 7, 11, 15], 9))   # [0, 1]
# 空间账：O(1)——这是双指针相对「用哈希表记补数」方案的差异点（无序数组用哈希，见 070 篇）

10. 什么时候应该 / 不应该用数组#

应该：按下标随机访问为主、尾部增删为主、需要与算法技巧（二分/双指针/前缀和）配合的场景——数组是默认起点；此外只要访问模式以「顺序扫一遍」为主，缓存局部性会让它持续优于看似理论更优的结构。

不应该：头部频繁插删（用 deque）；键值查找（用哈希表，070 篇）；中间频繁插删且顺序遍历为主（用链表，060 篇）——结构的选型由「最常见的操作位置」决定。

11. 与之前和之后的知识的关系#

• 往前：010 的大 O 语言在本文落地成三组实测，空间这本账在链式结构对照里第一次显形；
• 往后：链表 是连续内存的反面教材与互补者；二分查找 的 O(log n) 建立在数组 O(1) 随机访问之上；排序参考篇 的每种排序都在跟「搬移代价」搏斗；堆与优先队列 与 线段树 都在「读多写少」与「读写都多」之间接手前缀和交出的接力棒；
• 更远：Python list、Java ArrayList、C++ vector、Go slice——你未来学的每个语言的「数组」，都是本文动态数组思想的方言。

12. 官方文档#

• Python list 的时间复杂度 wiki：https://wiki.python.org/moin/TimeComplexity
• collections.deque（双端队列，头尾 O(1)）：https://docs.python.org/zh-cn/3/library/collections.html#collections.deque
• bisect（二分插入点，本文遮代码自检的手写对象）：https://docs.python.org/zh-cn/3/library/bisect.html

13. 自我检查#

• 能写出寻址公式并解释下标从 0 开始的原因；
• 能用实测数据说明「头插 O(n)、尾插均摊 O(1)」；
• 能解释倍增扩容与均摊 O(1) 的关系；
• 能说出缓存行机制，并用「链表 9 倍内存、1.6 倍顺序求和耗时」的实测解释连续内存的第二重红利；
• 能独立写出前缀和与首尾双指针，并说出各自的空间账；
• 能对三个数组技巧说出各自的适用信号与「哨兵消灭特判」手法。

本章总结#

数组用「连续内存」换来了 O(1) 随机访问，代价是中间插删的搬家；动态数组用倍增扩容把追加做到均摊 O(1)；缓存行机制再给连续内存一层寻址公式看不到的红利——链式结构用 9 倍内存也买不回来。技巧层面，前缀和示范了「预处理换查询」的交易结构，双指针示范了「每步淘汰一个候选」的降复杂度套路。选型只看一件事：你最常操作的位置在哪。下标从 0 开始不是惯例，是寻址公式的自然结论。

下一步#

进入 排序参考篇（参考层）：五种基础与主流排序算法的完整实现与对比，检验你刚建立的大 O 眼光。