内存与性能优化：从成本模型到页面 I/O

“更省内存”和“运行更快”不是同一件事。一个表示可能减少空槽，却增加一次查询要追踪的链接；一个操作可能偶尔复制整张表，却让很长一串操作的平均成本保持稳定；一棵树在主存里比较次数不多，放到外存后仍可能因为读取页面太多而变慢。

所以，优化不能从某个固定技巧出发。我们先明确输入规模与成本单位，再检查对象怎样落在数组和链接中，最后决定需要控制的是总步骤、辅助空间、空闲容量，还是页面读写次数。本文沿着这条线，把内存布局、表示选择、摊还分析、动态扩缩容和外存索引连成一套可复用的判断方法。

先把“快”和“省”变成可计算的问题

算法分析预测的是资源消耗。运行时间最常见，但内存、通信带宽和外部存储读写也可能才是主要约束。分析之前必须先回答两个问题：输入有多大，以及一次成本按什么计数。

输入规模不一定只有一个数字

排序时，数组元素个数 $n$ 通常就是自然的输入规模。大整数运算更适合用输入的总位数衡量，因为“一个整数”可能短到能放进一个机器字，也可能长到需要许多字。图则常用两个参数：顶点数 $|V|$ 与边数 $|E|$。若只写“图规模为 $n$”，稀疏图与稠密图的空间差异就会被藏起来。

输入规模的定义还约束了机器字。处理 $n$ 个可索引元素时，可以假设一个机器字有 $c\lg n$ 位，其中 $c\ge 1$ 是常数。这样，一个字足以保存数组下标，同时不会因为字长随输入任意增长而把巨量数据塞进“一次常数时间操作”。

RAM 模型适合做第一层分析

在顺序执行的 RAM 模型中，常见算术、装载、存储、复制、分支、调用与返回都按常数成本处理。这个抽象让我们能数“执行了多少个基本步骤”，而不用绑定某款处理器。

它也有边界：不能假设存在“一条指令完成排序”这种不现实操作；一般的幂运算也不能随意算作常数时间。更关键的是，RAM 模型不描述缓存与虚拟内存层次。因此，$Theta(n)$ 说明增长率，却不承诺两段 $Theta(n)$ 代码在具体机器上耗时相同。

时间成本与空间成本要分开计数

若第 $i$ 行伪代码每次成本为常数 $c_i$，执行 $t_i$ 次，那么总时间可以写成

随后再保留决定增长率的主导项。空间不能机械照搬这个乘法：一条语句每次访问 $m$ 个字，执行 $n$ 次，不代表它使用了 $mn$ 个不同的字。同一缓冲区可能被重复访问。分析空间时要数同时存活的独立存储单元，并区分输入本身、数据结构容量和算法额外申请的辅助空间。

可以把一次性能分析写成这张清单：

小测

对象、索引与空闲槽如何落进数组

指针不是实现链接结构的唯一办法。只要数组下标可以唯一指向一个槽，我们就能用下标合成“指针”，再用数组保存对象字段。这种表示把抽象对象与实际存储位置分开，也让内存预算变得可见。

多数组表示：同一下标拼成一个对象

假设双向链表节点有 key、next 和 prev 三个字段。可以为每个字段分别建数组：

key  = [·, 4, 1, ·, 16, ·, 9, ·]
next = [·, 3, ·, ·,  2, ·, 5, ·]
prev = [·, 5, 2, ·,  7, ·, ·, ·]

对同一个下标 $x$，key[x]、next[x]、prev[x] 合起来表示一个对象。next[x]=y 的含义是“下一个对象位于第 $y$ 槽”，而不是数组中紧邻的第 $x+1$ 槽。链表头也只需保存一个下标；再选一个不可能成为合法下标的值表示空指针。

这种布局适合同构对象：所有节点字段相同，各字段数组长度相同。若某个过程只扫描键，可以只访问 key；若要跟随链表，则读取 next 给出的索引。这里能严谨得到的结论是“扫描字段数组访问连续下标，跟随链接访问由索引序列决定”，至于具体缓存收益，仍要在目标机器上测量。

单数组表示：对象占据连续片段

另一种做法是在单个数组 $A$ 中为每个对象分配连续片段。若每个对象占 3 个位置，起始下标 $p$ 就是对象指针：

键值：A[p + 0]
后继：A[p + 1]
前驱：A[p + 2]

字段偏移固定，读取字段就是“基址加偏移”。这种方式还能在同一个数组里放长度不同的对象，但异构对象的分配、回收与碎片管理会更复杂。数据结构由同构节点组成时，多数组表示通常更容易管理。

空闲链表让分配和回收保持常数成本

若数组容量为 $m$、当前使用 $n$ 个对象，则剩余 $m-n$ 个槽可以串成单链表。全局变量 free 指向空闲链表头，空闲槽复用 next 字段记录下一空闲槽：

ALLOCATE-OBJECT()
  若 free 为空：报告空间不足
  x = free
  free = next[x]
  返回 x
 
FREE-OBJECT(x)
  next[x] = free
  free = x

两个操作都只修改常数个下标，所以成本为 $O(1)$。一个槽在任意时刻只能属于活动结构或空闲链表，不能同时属于两者。分配后，调用者必须写入活动对象需要的字段；回收时则只需重建空闲链，因为空闲槽的其他字段暂时没有语义。

小测

表示选择决定访问路径与空间上界

抽象接口相同，底层表示仍可能不同。选择时至少同时看三件事：结构空间是多少、一次操作访问哪些位置、是否需要额外的指针或辅助数组。

堆：树形关系压进连续数组

二叉堆在逻辑上是一棵近似完全二叉树，在物理上可以直接存进数组。若使用从 1 开始的下标，节点 $i$ 的关系由公式得到：

父子链接不需要额外指针。数组的 length 表示可用位置数，heap-size 表示当前属于堆的有效元素数，两者不能混为一谈。堆排序在输入数组之外只保留常数个元素，因此属于原地排序；这说明“逻辑上是树”并不必然意味着“每个节点都要单独分配并保存指针”。

哈希：用碰撞风险换取更小的索引范围

直接寻址表为键全集 $U$ 的每个可能值预留位置，需要 $Theta(|U|)$ 空间。当实际键集合 $K$ 远小于 $U$ 时，大多数槽会空着。哈希函数把键映射到 $m$ 个槽，可把存储量降到与实际键数同阶，但两个键可能落在同一槽。

链地址法让每个槽指向一条链表。它的空间为 $\Theta(m+n)$，包含 $m$ 个槽与 $n$ 个链表元素；当 $m=\Theta(n)$ 时，整体才是与实际键数同阶。查询先访问槽，再沿该槽的链接扫描。在简单均匀散列假设下，装载因子

等于平均链长，成功与失败查询的平均成本都是 $Theta(1+\alpha)$。若让 $m$ 与 $n$ 同阶，$alpha$ 保持常数，查询平均成本也保持常数。这里的“平均”依赖散列分布假设；最坏情况下，所有键进入同一条链，查询仍是 $Theta(n)$。

图：邻接表与邻接矩阵服务不同操作

邻接表用一个长度为 $|V|$ 的数组保存各顶点的邻居序列。其空间为

其中无向边会在两个顶点的邻接表中各出现一次。检查边 $(u,v)$ 是否存在，需要在 Adj[u] 中寻找 $v$。

邻接矩阵用 $|V|\times|V|$ 个位置保存边是否存在，空间为 $Theta(|V|^2)$，与实际边数无关。它能通过矩阵位置 $(u,v)$ 直接检查一条边，适合稠密图或频繁的边存在性查询。无权图的矩阵项可以只用一位；无向图矩阵关于主对角线对称，在某些实现中只保存一半。

图的顶点属性也可放在与顶点编号平行的数组中，例如 distance[u] 与 color[u]。这样，结构链接与算法状态分开，辅助空间能明确写成 $Theta(|V|)$，而不是含混地说“每个节点多几个字段”。

小测

摊还分析把偶发高成本放回完整序列

看到一次操作最坏为 $O(n)$，不能立刻断定做 $n$ 次就一定是 $O(n^2)$。关键要看昂贵操作是否能够连续发生，以及每个对象最多被昂贵地处理多少次。摊还分析研究任意操作序列的总成本，不要求输入服从概率分布。

聚合法：先求整段总成本

若任意 $n$ 次操作的总成本至多为 $T(n)$，则每次操作的摊还成本为 $T(n)/n$。

例如，栈增加 MULTIPOP(k)：它一次最多弹出 $k$ 个元素，看起来可能很贵。但从空栈开始的一串操作中，每个元素必须先被压入，并且一次压入对应的元素至多被弹出一次。因此，所有普通弹出与批量弹出的总次数不超过压入次数，$n$ 次操作总成本为 $O(n)$，每次摊还 $O(1)$。

二进制计数器也是同样思路。最低位每次加一都会翻转，下一位每两次翻转，再下一位每四次翻转。$n$ 次递增的总翻转数小于

所以一次递增虽然可能连续翻转许多位，摊还成本仍为 $O(1)$。

记账法：便宜时预存信用

记第 $i$ 次操作的实际成本为 $c_i$、摊还收费为 $\hat c_i$。为了让摊还总成本始终覆盖实际总成本，必须对任意前缀满足

多收的部分作为信用留在结构中，信用任何时刻都不能为负。栈可以在每次压入时收取 2 个单位：1 个支付本次压入，1 个留给未来弹出。这样普通弹出和批量弹出可记为 0，因为每个被弹出的元素都带着预付成本。

势能法：让整个状态保存“已预付工作”

对第 $i$ 次操作后的状态 $D_i$ 定义势能 $\Phi(D_i)$，摊还成本为

把 $n$ 次相加，中间势能会消去：

若初始势能为 0，且所有后续势能非负，摊还总成本就是实际总成本的上界。势能增加表示当前操作多付了一些；势能下降表示过去积累的额度正在支付当前高成本。势函数不是代码字段，它只是证明工具。

小测

动态表扩容为何能做到摊还常数时间

应用常常无法预先知道最终会保存多少对象。连续数组装满时，不能只在尾部“凭空多出一个槽”；需要申请更大的连续数组，把旧元素复制过去，再释放旧数组。触发扩容的那一次插入很贵，但扩容间隔决定了长期成本。

倍增策略把复制次数组成几何级数

设 num 是元素数，size 是容量。空表第一次插入时申请 1 个槽；表满时申请两倍容量，复制旧元素，再插入新元素：

TABLE-INSERT(T, x)
  若 T.size = 0：
    申请 1 个槽
    T.size = 1
  若 T.num = T.size：
    申请容量为 2 × T.size 的新表
    把旧表所有元素复制到新表
    释放旧表
    T.table = 新表
    T.size = 2 × T.size
  把 x 插入 T.table
  T.num = T.num + 1

按一次基础插入或复制一个元素计 1 个单位，第 $i$ 次插入若不扩容，成本为 1；若插入前已有 $i-1$ 个元素且容量正好装满，成本为 $i$。扩容发生在旧元素数为 $1,2,4,8,\ldots$ 时，因此 $n$ 次插入的总成本满足

所以任意 $n$ 次连续插入总成本为 $O(n)$，单次摊还成本至多为常数。倍增后装载因子至少约为 $1/2$，继续插入时逐渐升到 1，未用空间始终不超过总容量的常数比例。

势能解释“复制预算”从哪里来

只插入的动态表可使用

刚扩容后，元素数约为容量一半，势能接近 0；继续插入时，每次让势能增加 2；表再次装满前，势能已增长到足够支付旧元素复制。没有扩容的插入，实际成本为 1，势能增加 2，所以摊还成本为 3。触发扩容时，复制成本很高，但容量翻倍使势能大幅下降，摊还成本仍为 3。

小测

扩容与缩容之间需要迟滞区间

删除大量元素后缩小数组可以回收空闲容量，但缩容阈值不能紧贴扩容后的状态。否则，一小段插入与删除就会让容量来回变化，把整表复制反复触发。

在二分之一处缩容会发生抖动

假设满表容量为 $m$。再插入一个元素时扩到 $2m$，装载因子刚超过 $1/2$。如果规则是“低于 $1/2$ 就缩回一半”，接着做少量删除便会重新缩到 $m$；再做少量插入又扩到 $2m$。每次扩缩都要移动 $Theta(m)$ 个元素，而触发它们只需要常数次普通操作，于是可以构造总成本为 的操作序列。

问题不在“缩容”本身，而在两个阈值太近：扩容后没有足够多的后续删除为缩容积累预算，缩容后也没有足够多的插入为下一次扩容积累预算。

四分之一阈值留出安全距离

一种稳定策略是：插入满表时容量翻倍；删除使装载因子低于 $1/4$ 时，容量减半。扩容后装载因子回到约 $1/2$，缩容后也回到约 $1/2$。从 $1/2$ 走到 1 需要许多插入，从 $1/2$ 走到 $1/4$ 需要许多删除，因此两次整表搬迁之间总有足够多的普通操作。

装载因子定义为

空表释放全部存储，并单独约定其装载因子为 1。非空状态下，$alpha$ 有常数下界，所以未使用空间不会超过总空间的常数比例。

分段势函数同时支付两种搬迁

把半满状态视为理想点，势能取 0；越接近满表或四分之一满，势能越高：

当 $alpha=1$ 时，势能等于元素数，能支付扩容复制；当 $alpha=1/4$ 时，势能也等于元素数，能支付缩容搬迁。该势能从不为负。由此可证明，插入与删除的摊还成本都由常数控制，任意 $n$ 次操作的实际总成本为 $O(n)$。

缩容策略还要服从数据结构语义

动态表只是存储层，槽里可以组织栈、堆、哈希表或其他结构。复制时必须恢复对应不变式：

• 普通顺序表按逻辑顺序复制元素。
• 堆要保持有效堆区间与数组下标关系。
• 开放寻址哈希表不能简单逐槽照抄，因为容量改变后探查位置会改变，通常需要重新散列。
• 链地址哈希表若槽数改变，也要根据新槽数重新分配各链中的键。

因此，“搬了多少元素”给出扩缩容成本的主项，“怎样搬”还由上层结构决定。

小测

数据跨到外存后要按页面计算

当数据不能同时放进主存，优化目标会发生变化。外部存储按页面读取和写回，不是按单个键逐字节取用。一次页面访问通常带回一整块连续信息，所以运行时间应拆成两个部分：页面读写次数与页面进入主存后的 CPU 计算时间。

页面是外存算法的基本传输单位

外存对象被访问前，先把它所在页面读入主存；若对象被修改，再把页面写回。可以把过程写成：

x = 指向外存对象的引用
DISK-READ(x)
读取或修改 x 的字段
若修改过 x：DISK-WRITE(x)

若页面已经在主存，重复读取可以视为不产生新的外存访问。由于主存只能同时容纳有限页面，算法不能假设整个结构永久驻留。分析时先数读取或写入了多少页，再讨论页内比较与移动。

B-tree 用一个页面承载一个多路节点

二叉搜索树每个内部节点至多给出两个方向。B-tree 节点保存多个有序键；含有 $k$ 个键的内部节点可以有 $k+1$ 个孩子，把键空间分成多个区间。节点通常设计得接近一个页面大小，这样一次页面读取会带回许多分隔键与孩子引用。

若最小度数为 $t\ge 2$，每个非根节点至少有 $t-1$ 个键、至多有 $2t-1$ 个键，所有叶子位于同一深度。含 $n\ge1$ 个键的树高满足

较大的分支数增大了对数的底，从而减少树高。搜索每下降一层，通常只需再读一个节点页面；根若常驻主存，还能省去根页面的读取。因此，B-tree 的目标不是让页内比较为零，而是用更多页内比较换更少的页面访问。

把局部访问落实为“每页做足工作”

这里的局部性可以直接用页面模型表述：同一节点的有序键、孩子引用放在同一页，一次读取后在页内完成多路判断；若每个节点只放一个键，树会更高，搜索需要读取更多节点页面。

这也解释了前面表示选择的共同原则：

• 多数组或连续对象片段让一组相关字段可以落在紧凑区域，但跟随链接时访问顺序仍由索引决定。
• 数组堆用下标恢复树关系，不需要另读父子指针对象。
• 图邻接表把一个顶点的已有邻居收在一起，矩阵则把所有候选边位置规则排列。
• B-tree 进一步把“相关键放在一起”对齐到页面传输单位，并直接以 I/O 次数评估收益。

一套可执行的优化顺序

实际检查代码时，可以按下面步骤推进：

这套顺序的重点很朴素：先把成本单位定义对，再谈优化。否则，减少一次比较却增加一次页面读取，或为了节省空槽而制造频繁整表搬迁，都可能得到方向相反的结果。

小测