List Update 与 Move-to-Front

形式陈述

列表访问模型

有一个包含同一组元素的无序线性列表。访问当前位置为 $i$ 的元素需要支付 $i$ ；访问完成后，可以把刚访问的元素免费向前移动任意距离。除此之外，任意相邻元素交换都要支付 1。这个约定称为 full-cost 模型；若把访问成本写成 $i-1$ ，定理的低阶常数会相应改变，但证明结构不变。

Move-to-Front（MTF）在每次访问后都把该元素直接移到表头。它不估计长期频率，也不预知未来序列；状态完全由最近访问顺序形成。

与任意比较算法的竞争界

固定请求序列 $\sigma=(x_1,\ldots,x_m)$ ，并让比较算法 $A$ 可以知道未来。记 $A_{\mathrm{acc}}(\sigma)$ 为 $A$ 的访问位置成本之和， $X_A(\sigma)$ 为 $A$ 所做的付费相邻交换数， $F_A(\sigma)$ 为 $A$ 在访问后对该元素所做的免费向前相邻交换数。

令 $\Phi$ 是 MTF 当前排列与 $A$ 当前排列之间的逆序对数：一对元素在两份列表中的相对次序不同，就贡献 1。若初始排列可能不同，记初始势为 $\Phi_0$ 。经典势能分析给出

C_{\mathrm{MTF}}(\sigma) \le 2A_{\mathrm{acc}}(\sigma) +X_A(\sigma)-F_A(\sigma)-m +\Phi_0.

当两算法从同一排列开始时 $\Phi_0=0$ 。由于 $A$ 的总成本为 $A_{\mathrm{acc}}+X_A$ ，舍去右侧的负项并放宽 $X_A\le 2X_A$ ，得到

C_{\mathrm{MTF}}(\sigma) \le 2\bigl(A_{\mathrm{acc}}(\sigma)+X_A(\sigma)\bigr)+\Phi_0.

因此 MTF 对允许动态重排的离线最优算法也是 2-competitive；不同初始排列只产生与请求长度无关的加性项。

一次访问的逆序账本

处理某次请求 $x$ 时，设 $x$ 在 $A$ 的列表中位于第 $i$ 位，在 MTF 列表中位于第 $k$ 位。再设有 $t$ 个元素同时满足：它们在 MTF 中位于 $x$ 前面，却在 $A$ 中位于 $x$ 后面。MTF 把 $x$ 移到表头时，与这 $t$ 个元素之间原有的逆序被消去；其余 $k-t-1$ 个共同位于 $x$ 前面的元素与 $x$ 形成新逆序。所以

\Delta\Phi=(k-t-1)-t=k-2t-1,

其摊还访问成本为

k+\Delta\Phi=2(k-t)-1.

共同位于 $x$ 前面的元素有 $k-t-1$ 个，而 $A$ 中 $x$ 前面总共只有 $i-1$ 个元素，因此 $k-t\le i$ ，从而

k+\Delta\Phi\le 2i-1.

随后， $A$ 免费把 $x$ 向前交换一次，就会消去一个与 MTF 的逆序；每个付费相邻交换至多把势增加 1。把这些变化逐步计入，再对全部请求求和，就得到前面的全局不等式。这里使用的是 $\Phi=I$ ，即逆序对数本身；不需要额外乘 2。

直觉

MTF 把“刚被请求”当作短期局部性的信号。一个热点第一次可能在列表深处，但访问后立即来到表头；连续热点的后续成本都降为 1。热点发生切换时，新热点也会自动前移，不需要维护频率计数或显式时间戳。

逆序势衡量的不是一份列表自身有多乱，而是在线列表与比较算法的排列差异。MTF 为寻找 $x$ 越过的元素越多，本次访问越贵；同一批元素也正是势变化的全部来源。于是实际成本和“靠近比较算法”或“远离比较算法”的变化可以放在同一本账上结算。

访问 b 后移到表头而与比较列表的逆序势保持不变 — Move-to-Front 的访问与逆序势账本

例子与边界

设 MTF 当前列表为 [c,a,b,d]，比较算法 $A$ 的列表为 [a,b,c,d]，本次请求 b。这里 $k=3$ 、 $i=2$ ；在 MTF 中位于 b 前面但在 $A$ 中位于它后面的只有 c，所以 $t=1$ 。MTF 把 b 移到表头时

\Delta\Phi=3-2\cdot1-1=0,

实际成本为 3，摊还成本仍为 3，而 $2i-1=3$ ，这一步恰好取等。势没有变化并不表示列表没变，而是新增和消去的逆序数量刚好抵消。

模型边界必须固定。经典免费操作只允许“刚访问的元素向前移动”；若允许免费任意重排整个列表，比较基准会被彻底改变。若交换具有非单位权重、元素大小不同或访问代价不是位置的线性函数，也需要新的势函数或新的竞争界。

MTF 的保证是序列总成本，不是逐次延迟上界。一个长期未访问的元素第一次仍可能花费线性成本。static optimum 只选择一个固定排列，dynamic optimum 则能随序列付费调整；两种基准对应不同问题，不能只写“优于最优排列”而省略最优算法允许的操作。

Transpose 每次只把访问项前移一位，Frequency Count 按累计次数排序。它们也会让热点前移，却不因此自动继承 MTF 的 2-竞争性；竞争定理依赖具体状态更新与势变化，而不是“具有自调整性”这一宽泛描述。

推论与应用

MTF 是自调整数据结构和竞争分析的早期范例。证明中的势同时依赖在线算法与比较算法，展示了势能法不仅能分析单个数据结构的摊还操作，也能追踪两个动态状态之间的距离。

在 paging 的阶梯成本模型中，列表前 $k$ 个位置可视为缓存，MTF 的最近访问顺序对应 LRU。两者的具体成本函数不同，但“最近访问元素移到最前、最久未用元素逐渐后退”的状态语义相同；从 list update 迁移结论时仍需重新核对成本模型和允许操作。

参考资料

Daniel D. Sleator and Robert E. Tarjan, “Amortized Efficiency of List Update and Paging Rules,” Communications of the ACM 28(2), 1985, pp. 202–208.
Allan Borodin and Ran El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998, Chapter 3.

形式陈述 ​

列表访问模型 ​

与任意比较算法的竞争界 ​

一次访问的逆序账本 ​

反向链接

形式陈述

列表访问模型

与任意比较算法的竞争界

一次访问的逆序账本