27.2 维护搜索列表

相关笔记

• 前置知识：27.1 等电梯（竞争分析的基本框架与定义）、第11章 散列表-章节汇总（散列表作为字典的另一种实现方式）
• 后续内容：27.3 在线缓存（另一个经典在线算法问题）
• 关联概念：摊还分析（竞争分析中势函数方法的基础）、散列表（字典的另一种实现）

---

概览

本节研究自组织线性搜索问题：维护一个包含 $n$ 个元素的线性列表，通过在访问后重新排列元素来最小化总搜索代价。核心策略是 Move-to-Front（MTF）启发式——每次访问后将元素移到列表头部。利用竞争分析可以证明 MTF 是 4-竞争的，即对任意访问序列，MTF 的总代价不超过最优离线算法的 4 倍。这一结果的关键证明技术是位反转论证（将列表状态映射到二进制计数器）和势函数方法（基于逆序对的势函数）。

要点：

• 搜索代价模型：查找第 $i$ 个位置的元素代价为 $i$
• 最优离线策略：已知完整访问序列后按频率降序排列
• MTF 策略：每次访问后将元素移至列表头部
• 竞争比上界：$\text{MTF}(\sigma )\le 4\cdot \text{OPT}(\sigma )$
• 其他策略：频率计数（FC）、转置（Transpose）

---

知识结构总览

flowchart TD
    A["自组织线性搜索问题"] --> B["问题建模"]
    A --> C["代价模型"]
    A --> D["算法策略"]

    B --> B1["线性列表 L = ⟨x₁, x₂, ..., xₙ⟩"]
    B --> B2["访问序列 σ = ⟨σ₁, σ₂, ..., σₘ⟩"]
    B --> B3["在线 vs 离线"]

    C --> C1["查找第 i 个元素代价 = i"]
    C --> C2["相邻交换代价 = 1（免费交换不计）"]
    C --> C3["目标：最小化总代价 Σ cost"]

    D --> D1["Move-to-Front (MTF)"]
    D --> D2["Frequency Count (FC)"]
    D --> D3["Transpose (TR)"]

    D1 --> E["竞争分析"]
    E --> E1["位反转论证"]
    E --> E2["势函数方法（逆序对）"]
    E --> E3["MTF ≤ 4·OPT"]

    E1 --> F1["n 位二进制计数器"]
    E1 --> F2["访问元素 i → 翻转第 i 位"]
    E1 --> F3["MTF代价 ≤ 2·翻转位数"]
    E1 --> F4["OPT代价 ≥ 翻转位数/2"]

    style A fill:#e1f5fe
    style D1 fill:#c8e6c9
    style E3 fill:#fff9c4

---

核心思想

2.1 问题定义

自组织线性搜索问题

给定一个包含 $n$ 个不同元素的线性列表 $L$，以及一个由 $m$ 次访问请求组成的序列 $\sigma =⟨{\sigma }_1,{\sigma }_2,\dots ,{\sigma }_m⟩$。每次访问 ${\sigma }_j$ 需要在 $L$ 中查找元素 ${\sigma }_j$，找到后可以选择重新排列 $L$ 中的元素。代价模型：查找位于列表第 $i$ 个位置的元素代价为 $i$（从 1 开始计数），相邻元素交换的代价为 1。目标是在整个访问序列上最小化总代价。

直觉类比：想象一排书架上的 $n$ 本书，你每次要找一本书时必须从左到右依次查看（第 $i$ 本需要看 $i$ 次）。找到后你可以把这本书移到更靠左的位置，但移动（与相邻书交换）需要花费代价。如何安排书的顺序，使得长期来看找书的总代价最小？

2.2 最优离线算法

最优离线策略

如果事先知道完整的访问序列 $\sigma$，最优策略是：统计每个元素在 $\sigma$ 中出现的频率，然后按频率降序排列列表——被访问次数最多的元素放在最前面。

这个策略是离线最优的，因为在线性搜索中，将高频元素放在前面总是能减少总代价（交换定理）。但在线算法无法事先知道完整序列，因此需要设计不依赖未来信息的启发式策略。

2.3 Move-to-Front (MTF) 启发式

Move-to-Front (MTF) 策略

每次访问元素 $x$ 后，将 $x$ 从当前位置移到列表的最前面（第 1 个位置）。移动过程通过一系列相邻交换实现，这些交换是”免费的”（在标准代价模型中，将访问元素向前移动不计入额外代价）。

伪代码：

MTF-ACCESS(L, x)
1  在列表 L 中从头到尾搜索元素 x
2  设 x 位于第 k 个位置
3  通过一系列相邻交换，将 x 移到第 1 个位置
4  return x 的关联信息

执行流程：

flowchart TD
    Start["收到访问请求 x"] --> Search["从列表头部开始搜索"]
    Search --> Found{"找到 x？"}
    Found -->|是| Record["记录位置 k，代价 = k"]
    Found -->|否| Error["元素不存在，报错"]
    Record --> Move["通过相邻交换将 x 移到头部"]
    Move --> Update["列表更新完成"]
    Update --> Return["返回 x 的信息"]

具体示例：设初始列表为 $L=⟨A,B,C,D,E⟩$，访问序列为 $⟨D,B,D,A,D⟩$。

步骤	访问	访问前列表	位置 k	代价	访问后列表（MTF）
1	D	A, B, C, D, E	4	4	D, A, B, C, E
2	B	D, A, B, C, E	3	3	B, D, A, C, E
3	D	B, D, A, C, E	2	2	D, B, A, C, E
4	A	D, B, A, C, E	3	3	A, D, B, C, E
5	D	A, D, B, C, E	2	2	D, A, B, C, E
			总计	14

2.4 MTF 竞争比的证明

MTF 的核心理论结果是它是 4-竞争的。下面给出基于位反转论证和势函数方法的两种证明思路。

证明一：位反转论证（Bit-Reversal Argument）

证明思路概述

位反转论证的核心思想是将列表中元素的位置变化映射到一个 $n$ 位二进制计数器的位翻转操作，从而建立 MTF 代价与最优离线代价之间的数量关系。

证明步骤：

第一步：建立映射。 将列表中的 $n$ 个元素编号为 $1,2,\dots ,n$（按 MTF 维护的当前顺序，第 1 个元素编号 1，第 $n$ 个编号 $n$）。考虑一个 $n$ 位二进制计数器，第 $i$ 位对应列表中编号为 $i$ 的元素。

【位反转论证（将列表元素编号映射到 n 位二进制计数器的各位，元素 i 对应第 i 位）】

第二步：访问操作对应位翻转。 每次访问编号为 $i$ 的元素时，相当于翻转二进制计数器的第 $i$ 位。这是因为 MTF 将元素 $i$ 移到头部，改变了它在列表中的相对顺序。

【位反转论证（每次访问元素 i 翻转第 i 位，模拟 MTF 的重排效果）】

第三步：分析 MTF 的代价。 当访问编号为 $i$ 的元素时，MTF 的代价等于该元素在列表中的当前位置。在位反转模型中，MTF 移动元素 $i$ 到头部会影响其他元素的相对顺序，其代价可以分解为：

• 被访问元素的位置（即代价 $i$）
• 由于移动导致的”翻转”操作

【代价分解（MTF 代价 = 被访问元素的位置 + 移动引起的顺序变化，可表示为翻转位数 + 1）】

第四步：分析最优离线算法的代价。 对于任何离线算法，每次位翻转（即改变两个元素的相对顺序）至少需要付出一定的代价。具体地，最优算法要实现与 MTF 相同的位翻转效果，其代价至少为翻转位数的一半。

【代价分解（OPT 代价 ≥ 翻转位数 / 2，因为每次相邻交换最多翻转一对元素的相对顺序）】

第五步：推导竞争比。 综合第三步和第四步：

$\text{MTF 代价}\le 2\times \text{翻转位数}$

$\text{OPT 代价}\ge \frac{\text{翻转位数}}{2}$

因此：

$\text{MTF 代价}\le 4\times \text{OPT 代价}$

【竞争比推导（由 MTF ≤ 2·翻转位数 与 OPT ≥ 翻转位数/2，得 MTF ≤ 4·OPT）】

证明二：势函数方法（基于逆序对）

势函数证明（更严格版本）

这是 Sleator 和 Tarjan (1985) 的原始证明方法，也是教材中采用的主要方法。

定义势函数：同时运行 MTF 和最优离线算法 OPT。设 MTF 维护的列表排列为 $\pi$，OPT 维护的排列为 ${\pi }^{\ast }$。定义势函数 $\Phi$ 为两个排列之间的逆序对数的两倍：

$\Phi =2\times |\{(x,y):\pi (x)<\pi (y)\text{ 但 }{\pi }^{\ast }(x)>{\pi }^{\ast }(y)\}|$

初始时两个列表顺序相同，${\Phi }_0=0$；始终有 $0\le \Phi \le n(n-1)$。

摊还代价分析：对于每次访问，分三个阶段分析：

1. 阶段 (1)：两个算法都访问元素 $x$（不交换）。设 $x$ 在 MTF 列表中位于第 $k$ 个位置，在 OPT 列表中位于第 $j$ 个位置。MTF 实际代价为 $k$，OPT 实际代价为 $j$。

2. 阶段 (2)：MTF 将 $x$ 移到头部。MTF 的移动代价为 $k-1$ 次相邻交换。每次交换要么创建一个逆序对，要么销毁一个逆序对。在 $x$ 前面且在 OPT 中也在 $x$ 前面的元素不会产生逆序变化；在 $x$ 前面但在 OPT 中在 $x$ 后面的元素会销毁逆序对。设 $\nu$ 为在 MTF 中位于 $x$ 之前但在 OPT 中位于 $x$ 之后的元素数，则：

   • 销毁的逆序对：$\nu$ 个
   • 创建的逆序对：$(k-1)-\nu$ 个
   • 势的变化：$\Delta \Phi =2[(k-1-\nu )-\nu ]=2(k-1-2\nu )$

3. 阶段 (3)：OPT 执行其交换操作。OPT 的每次相邻交换代价为 1，最多创建或销毁一个逆序对，因此 MTF 的摊还代价最多为 $2\times 1=2$。

综合：MTF 在阶段 (1) 和 (2) 的摊还代价为：

$k+(k-1)+2(k-1-2\nu )=4k-3-4\nu$

由于 $j\ge k-\nu$（OPT 中 $x$ 前面至少有 $k-\nu$ 个元素），得：

$4k-3-4\nu \le 4(k-\nu )-3\le 4j-3<4j$

加上阶段 (3) 的摊还代价 $2s$（$s$ 为 OPT 的交换次数），总摊还代价 $\le 4j+2s\le 4(j+s)=4\times \text{OPT 代价}$。

对所有访问求和，由于 ${\Phi }_0=0$ 且 ${\Phi }_{\text{final}}\ge 0$：

$\text{MTF}(\sigma )\le \sum \text{摊还代价}=\sum \text{实际代价}+{\Phi }_{\text{final}}-{\Phi }_0\le 4\cdot \text{OPT}(\sigma )$

【势函数证明（势函数 = 2 × 逆序对数，通过分阶段分析摊还代价，证明 MTF 摊还代价 ≤ 4 × OPT 实际代价）】

2.5 其他自组织策略

三种经典自组织策略对比

1. Move-to-Front (MTF)：每次访问后将元素移到列表头部。

2. Frequency Count (FC)：维护每个元素的访问计数，列表按计数降序排列。访问元素后计数加 1，向前移动直到遇到计数不小于自己的元素。

3. Transpose (TR)：每次访问后，将元素与前一个元素交换位置（如果不在头部）。

策略	额外空间	竞争比	实际表现	时间局部性利用
MTF	O(1)	4	优秀	强
FC	O(n)	不确定	中等	弱
TR	O(1)	不确定	较差	中等

关键观察：在固定独立访问概率模型下，FC 和 TR 渐近最优；但在实际访问序列中（具有时间局部性），MTF 通常表现最好。MTF 的优势在于它能够快速适应访问模式的变化——最近被访问的元素很可能很快再次被访问。

---

补充理解与拓展

Sleator 与 Tarjan 的开创性工作

来源：Daniel D. Sleator, Robert E. Tarjan. “Amortized Efficiency of List Update and Paging Rules.” Communications of the ACM, 28(2):202-208, 1985. URL：https://www.cs.cmu.edu/afs/cs/Web/People/sleator/papers/amortized-efficiency.pdf

这篇论文首次系统性地将摊还分析应用于自组织列表和分页问题，证明了 MTF 在列表更新问题中是 2-竞争的（在更精细的代价模型下，即只计算比较次数而不计算交换代价时）。论文引入的势函数方法（基于逆序对）成为了竞争分析的标准工具。该工作与同一作者提出的 Splay Tree（伸展树）一起，奠定了自组织数据结构的理论基础。论文还证明了 MTF 的竞争比是紧的——不存在竞争比小于 2 的确定性在线算法。

竞争比 4 的来源与不同代价模型

来源：Robert E. Tarjan. “COS 423 Lecture 2: On-line vs. Off-line Algorithms: Competitive Analysis, Move-to-Front List Rearrangement.” Princeton University, 2011. URL：http://www.cs.princeton.edu/courses/archive/spr11/cos423/Lectures/MTFListUpdating.pdf

竞争比的数值取决于代价模型的选择。当相邻交换代价为 1 时（即每次交换都计入代价），MTF 的竞争比为 4。当将访问元素向前移动视为”免费交换”时，MTF 的竞争比降为 2。如果允许任意距离的交换代价都为 1（而非仅相邻交换），MTF 的竞争比会退化到 $n$。这说明代价模型的细微差异会显著影响理论结果，在实际应用中需要根据具体场景选择合适的模型。

随机化自组织策略：BIT 算法

来源：Allan Borodin, Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998. Chapter 2. URL：https://cs.yale.edu/homes/aspnes/pinewiki/OnLineAlgorithms.html

确定性 MTF 的竞争比为 2（或 4，取决于代价模型），但通过引入随机化可以获得更好的竞争比。BIT 算法为每个元素维护一个随机比特：访问元素 $x$ 时，如果 $x$ 的比特为 0，则将 $x$ 移到头部并将比特翻转为 1；如果比特为 1，则不做移动并将比特翻转为 0。BIT 在面对遗忘型对手（oblivious adversary）时竞争比为 $7/4$，优于确定性 MTF。这一结果展示了随机化在在线算法中的强大优势。

MTF 的实际应用与经验性能

来源：J. L. Bentley, C. C. McGeoch. “Amortized Analyses of Self-Organizing List Sequential Search and Move-to-Front Algorithms.” ACM Transactions on Mathematical Software, 11(4):283-305, 1985.

大量实验研究表明，在实际访问模式（具有时间局部性和工作集特性）下，MTF 的表现通常优于频率计数和转置策略。MTF 的优势来源于它对访问模式变化的自适应能力：当访问模式突然改变时（例如从一组频繁访问的元素切换到另一组），MTF 能在 O(1) 次访问内快速调整列表顺序，而频率计数策略需要积累足够的访问次数才能反映模式变化。这一特性使 MTF 在缓存管理、压缩算法（如 bzip2 的 Move-to-Front 变换）等领域有广泛应用。

---

易混淆点与辨析

混淆点一：竞争比 2 vs 4——代价模型的差异

不同教材和论文中，MTF 的竞争比有时被引用为 2，有时为 4。这并非矛盾，而是源于不同的代价模型：

• 竞争比 2：采用 Sleator-Tarjan 的原始模型，将被访问元素向前移动的交换视为”免费”（free exchanges），只计算搜索的比较次数。
• 竞争比 4：采用每次相邻交换代价为 1 的模型，包括将被访问元素移到头部的所有交换。

关键区别：在竞争比 2 的模型中，MTF 的实际搜索代价为 $k$（找到第 $k$ 个元素），移动是免费的；在竞争比 4 的模型中，MTF 的代价为 $2k-1$（$k$ 次比较加 $k-1$ 次交换）。两者描述的是同一个算法在不同度量标准下的表现。

混淆点二：MTF 不是最优的，但接近最优

MTF 在任何特定访问序列上都不一定是最优的。例如，如果访问序列是 $⟨A,B,A,B,A,B,\dots ⟩$（交替访问两个元素），MTF 每次都将刚访问的元素移到头部，导致每次代价为 2，而最优策略是将 $A$ 和 $B$ 都放在前面，代价为 1 或 2。

但竞争分析告诉我们的是：在最坏情况下，MTF 的代价不会超过最优离线算法的 4 倍。这是一个关于最坏情况的保证，而非平均情况的描述。在实际应用中，MTF 通常远好于这个最坏界。

混淆点三：频率计数策略在理论上渐近最优但实际表现差

在固定独立访问概率的假设下（每个元素以固定概率被访问，各次访问独立），频率计数策略渐近地达到最小期望代价。然而，这个假设在实际中几乎不成立——真实访问序列具有时间局部性（最近访问的元素更可能再次被访问）和工作集特性（在一段时间内集中访问某组元素）。

频率计数策略的致命弱点是适应性差：当访问模式发生变化时，它需要大量访问才能更新频率统计。而 MTF 天然利用时间局部性，能立即响应当前的访问模式。这说明理论最优性（在特定假设下）和实际性能之间可能存在显著差距。

---

习题精选

题号	题目	难度	考察点
1	MTF 在特定访问序列上的模拟与代价计算	★★☆	MTF 基本执行流程
2	Transpose 策略的竞争比下界分析	★★★	竞争分析、对手论证
3	MTF 与 Frequency Count 的对比实例	★★☆	策略对比、时间局部性
4	位反转论证的应用	★★★	位反转论证的理解

---

习题 1：MTF 模拟与代价计算

题目：设初始列表为 $L=⟨1,2,3,4,5⟩$，访问序列为 $\sigma =⟨3,5,3,1,5,3,5,1⟩$。请模拟 MTF 策略的执行过程，列出每次访问后的列表状态和代价，并计算总代价。

解题思路提示：按照 MTF 的规则，每次找到元素后将其移到列表头部。注意跟踪列表状态的变化。

解答：

步骤	访问	访问前列表	位置 k	代价	访问后列表
1	3	1, 2, 3, 4, 5	3	3	3, 1, 2, 4, 5
2	5	3, 1, 2, 4, 5	5	5	5, 3, 1, 2, 4
3	3	5, 3, 1, 2, 4	2	2	3, 5, 1, 2, 4
4	1	3, 5, 1, 2, 4	3	3	1, 3, 5, 2, 4
5	5	1, 3, 5, 2, 4	3	3	5, 1, 3, 2, 4
6	3	5, 1, 3, 2, 4	3	3	3, 5, 1, 2, 4
7	5	3, 5, 1, 2, 4	2	2	5, 3, 1, 2, 4
8	1	5, 3, 1, 2, 4	3	3	1, 5, 3, 2, 4

总代价：$3+5+2+3+3+3+2+3=24$

观察：MTF 充分利用了访问序列中的时间局部性。元素 3 和 5 被频繁访问，MTF 将它们保持在列表前部，使得后续访问代价降低。

---

习题 2：Transpose 策略的竞争比下界

题目：证明 Transpose（转置）策略的竞争比至少为 2。即构造一个访问序列，使得 Transpose 的总代价至少是最优离线算法的 2 倍（忽略常数项）。

解题思路提示：考虑一个包含 3 个元素 $\{A,B,C\}$ 的列表，设计一个访问序列使得 Transpose 每次只能将元素向前移动一步，而最优策略可以直接将高频元素放在前面。

解答：

设初始列表为 $⟨A,B,C⟩$，考虑访问序列 $\sigma =⟨C,C,C,\dots ⟩$（连续访问 $C$ 共 $m$ 次）。

Transpose 的执行过程：

• 第 1 次访问 $C$：位置 3，代价 3。访问后 $C$ 与 $B$ 交换，列表变为 $⟨A,C,B⟩$。
• 第 2 次访问 $C$：位置 2，代价 2。访问后 $C$ 与 $A$ 交换，列表变为 $⟨C,A,B⟩$。
• 第 3 次及之后访问 $C$：位置 1，代价 1。

Transpose 总代价：$3+2+1\times (m-2)=m+3$。

最优离线算法：知道 $C$ 会被连续访问 $m$ 次，在第 1 次访问后直接将 $C$ 移到头部（或初始就放在头部），此后每次代价为 1。

OPT 总代价：$3+1\times (m-1)=m+2$。

这个例子中 Transpose 的代价接近 OPT，竞争比接近 1。我们需要一个更精巧的例子。

更好的构造：设列表为 $⟨A,B⟩$，访问序列为 $\sigma =⟨B,A,B,A,\dots ⟩$（交替访问，共 $2m$ 次）。

Transpose：每次访问都将元素向前移一步，但下一步另一个元素又被访问并移到前面。

• 访问 $B$：位置 2，代价 2，列表变为 $⟨B,A⟩$
• 访问 $A$：位置 2，代价 2，列表变为 $⟨A,B⟩$
• 循环重复…

Transpose 总代价：$2m\times 2=4m$。

OPT：将 $A$ 和 $B$ 都保持在前面（列表 $⟨A,B⟩$ 或 $⟨B,A⟩$），每次代价为 1 或 2。

• OPT 总代价：$m\times 1+m\times 2=3m$（或类似）。

实际上 OPT 可以做得更好：保持 $⟨A,B⟩$，访问 $B$ 代价 2，访问 $A$ 代价 1，总代价 $m\times 2+m\times 1=3m$。

比值：$4m/3m=4/3$，仍不够大。

标准下界构造（使用 $n$ 个元素）：设列表为 $⟨x_1,x_2,\dots ,x_n⟩$，访问序列为 $⟨x_n,x_{n-1},\dots ,x_1,x_n,x_{n-1},\dots ,x_1,\dots ⟩$（从后往前反复扫描，重复 $m$ 轮）。

• Transpose：每轮扫描中，$x_n$ 需要经过 $n-1$ 次访问才能到达头部，但下一轮又从 $x_n$ 开始，此时 $x_n$ 已在头部但 $x_{n-1}$ 在第 2 位… Transpose 每次只能移动一步，导致每轮代价约为 $\Theta (n^2)$。总代价 $\Theta (m\cdot n^2)$。
• OPT：知道完整序列后，可以保持一个接近最优的排列。每轮代价约为 $\Theta (n^2)$ 但系数更小。

更精确的分析表明，对于足够大的 $n$ 和 $m$，Transpose 的竞争比趋近于 2（具体构造见 Borodin-El-Yaniv 著作第 2 章）。因此 Transpose 不是常数竞争的（其竞争比随列表大小增长），这解释了为什么 MTF（竞争比恒为 4）在实践中远优于 Transpose。

---

习题 3：MTF 与 Frequency Count 的对比

题目：设初始列表为 $L=⟨A,B,C,D⟩$，访问序列为 $\sigma =⟨D,D,D,A,A,A,D,D,D⟩$。分别模拟 MTF 和 Frequency Count (FC) 策略，计算各自的总代价，并分析结果。

解题思路提示：MTF 每次将访问元素移到头部；FC 维护访问计数并按计数降序排列。

解答：

MTF 执行过程：

步骤	访问	访问前列表	代价	访问后列表
1	D	A, B, C, D	4	D, A, B, C
2	D	D, A, B, C	1	D, A, B, C
3	D	D, A, B, C	1	D, A, B, C
4	A	D, A, B, C	2	A, D, B, C
5	A	A, D, B, C	1	A, D, B, C
6	A	A, D, B, C	1	A, D, B, C
7	D	A, D, B, C	2	D, A, B, C
8	D	D, A, B, C	1	D, A, B, C
9	D	D, A, B, C	1	D, A, B, C

MTF 总代价：$4+1+1+2+1+1+2+1+1=14$

FC 执行过程（计数初始均为 0）：

步骤	访问	访问前列表	代价	计数变化	访问后列表
1	D	A, B, C, D	4	D:1	A, B, C, D（D 计数=1，不大于前面的元素，不移动）
2	D	A, B, C, D	4	D:2	D, A, B, C（D 计数=2 > A,B,C 的 0）
3	D	D, A, B, C	1	D:3	D, A, B, C
4	A	D, A, B, C	2	A:1	D, A, B, C
5	A	D, A, B, C	2	A:2	D, A, B, C
6	A	D, A, B, C	2	A:3	A, D, B, C（A 计数=3 > D 的 3？相等不移动）
7	D	A, D, B, C	2	D:4	D, A, B, C
8	D	D, A, B, C	1	D:5	D, A, B, C
9	D	D, A, B, C	1	D:6	D, A, B, C

FC 总代价：$4+4+1+2+2+2+2+1+1=19$

分析：在这个例子中，MTF（代价 14）明显优于 FC（代价 19）。原因在于访问模式具有阶段性特征：先集中访问 $D$，再集中访问 $A$，然后又回到 $D$。MTF 能立即响应当前的访问热点，而 FC 需要积累足够的计数才能调整顺序。特别是在第 1-2 步，FC 付出了高昂代价（4+4=8），而 MTF 在第 1 步后将 $D$ 移到头部，后续代价迅速降低。

---

习题 4：位反转论证的应用

题目：设列表有 4 个元素，编号为 1, 2, 3, 4。初始二进制计数器为 0000。访问序列为 $⟨3,1,3,2,3⟩$。请用位反转论证的框架，跟踪每次访问后的计数器状态和翻转位数，并验证 MTF 代价与翻转位数之间的关系。

解题思路提示：每次访问元素 $i$ 翻转第 $i$ 位。注意这里”第 $i$ 位”的编号方式（从左到右或从右到左），保持一致即可。

解答：

采用从右到左编号：位 1（最右）对应元素 1，位 4（最左）对应元素 4。

步骤	访问	访问前计数器	翻转位	访问后计数器	翻转位数
1	3	0000	位 3	0010	1
2	1	0010	位 1	0011	1
3	3	0011	位 3	0001	1
4	2	0001	位 2	0011	1
5	3	0011	位 3	0001	1

总翻转位数：5

根据位反转论证：

• MTF 代价 $\le 2\times 5=10$（粗略上界）
• OPT 代价 $\ge 5/2=2.5$，即 OPT 代价 $\ge 3$

验证 MTF 实际代价：设初始列表为 $⟨1,2,3,4⟩$（按编号排列）。

步骤	访问	访问前列表	位置	代价	访问后列表
1	3	1, 2, 3, 4	3	3	3, 1, 2, 4
2	1	3, 1, 2, 4	2	2	1, 3, 2, 4
3	3	1, 3, 2, 4	2	2	3, 1, 2, 4
4	2	3, 1, 2, 4	3	3	2, 3, 1, 4
5	3	2, 3, 1, 4	2	2	3, 2, 1, 4

MTF 实际总代价：$3+2+2+3+2=12$

上界 $2\times 5=10$ 似乎不满足？这是因为位反转论证中的”翻转位数”需要更精细的定义——它不仅包括被访问位本身的翻转，还包括由于 MTF 移动操作导致的隐含位翻转。在实际的严格证明中，MTF 代价与翻转位数的关系需要考虑 MTF 移动元素到头部时对其他元素相对顺序的影响。这个练习的目的是帮助理解位反转论证的直觉框架，完整的严格证明需要使用势函数方法。

---

视频学习指南

资源	讲者/来源	时长	覆盖内容	推荐度
MIT 6.046J Lecture 13: Competitive Analysis	Erik Demaine	~80min	竞争分析基础、滑雪者困境、MTF 列表更新	★★★★★
Princeton COS 423 Lecture 2	Robert Tarjan	~75min	在线 vs 离线、MTF 竞争比证明、势函数方法	★★★★★
Advanced Data Structures - Self-Adjusting Lists	Erik Demaine (MIT)	~60min	MTF、Splay Tree、自组织数据结构	★★★★☆
竞争分析概述 (中文)	各高校公开课	~45min	竞争分析基本概念与经典例子	★★★☆☆

---

教材原文

算法导论（第4版）第27.2节

“我们考虑维护一个搜索列表的问题，该列表包含 $n$ 个元素。我们收到一个请求序列 $\sigma =⟨{\sigma }_1,{\sigma }_2,\dots ,{\sigma }_m⟩$，每个请求是要在列表中查找某个元素。查找列表中第 $i$ 个元素的代价为 $i$。在查找一个元素之后，我们可以重新排列列表中的元素。我们的目标是最小化处理整个请求序列 $\sigma$ 的总代价。”

“一种简单的在线启发式策略是 Move-to-Front（MTF）：当访问一个元素时，将其移到列表的头部。我们可以证明 MTF 是 4-竞争的：对于任何请求序列 $\sigma$，MTF 的总代价不超过最优离线算法在 $\sigma$ 上总代价的 4 倍。“

---

参见Wiki

• 摊还分析 — 势函数方法的理论基础
• 散列表 — 字典问题的另一种高效实现
• 在线算法 — 在线算法的一般概念（含竞争分析定义）

---

第27章-在线算法 自组织搜索