List Update 与 Move-to-Front

成本模型与算法 ​

在竞争分析公理库竞争分析Competitive analysis在同一请求序列上比较在线算法总成本与预知未来的离线最优。采用的 full-cost 模型里，无序列表中访问第 $i$ 个元素成本为 $i$（有的文献用 $i-1$，常数需随约定调整）。访问后可把该元素免费向前移动任意位置；其他相邻交换每次成本 1。Move-to-Front 在每次访问后把该元素移到表头。

逆序势 ​

同时观察 MTF 列表与离线 OPT 列表。令 $\mathrm{\Phi }$ 为两排列之间的 inversion 数。访问元素 $x$ 时，设 MTF 前有 $a$ 项、其中 $b$ 项在 OPT 中位于 $x$ 后。MTF 成本 $a+1$，移到表头使势变化约为 $(a-b)-b=a-2b$ 的相反约定量；结合 OPT 访问位置可推出本步摊还成本不超过 OPT 本步访问与付费交换成本的 2 倍。求和后

$${\mathrm{cost}}_{MTF}\le 2{\mathrm{cost}}_{OPT}+{\mathrm{\Phi }}_0.$$

势同时比较两个算法状态，这不只是单结构摊还分析。

热点例子 ​

字典列表最初把某命令放在尾部；它第一次访问昂贵，移到表头后连续访问均为 1。若热点切换，新的热点也会前移，不需要预知静态频率。这个序列敏感性不同于事先按频率排好的 static optimum。

边界 ​

若允许访问后免费任意重排整个列表，或交换成本不同，2-competitive 证明不再对应模型。摊还便宜不代表每次延迟低；长尾元素首次访问仍线性。static optimum 只选一个固定排列，dynamic optimum 可随请求付费调整，比较基准必须写明。

势变化的对象 ​

访问 $x$ 后，MTF 只改变 $x$ 与原先排在它前面的元素之间的相对次序；其他 pair 的 inversion 状态不变。把这些元素按其在 OPT 中位于 $x$ 前/后分类，就能精确计算势增减，并与 OPT 访问位置连接。若实现还在访问前做付费交换，这些交换每次至多改变一个 inversion，也要计入步成本。

Transpose 规则只把访问项向前交换一位，虽然更保守，却没有同样的 2-competitive 保证；自调整规则不能仅凭“热点会前移”互换定理。

一次访问的逆序账本 ​

设 MTF 当前列表为 [c,a,b,d]，比较算法 $A$ 为 [a,b,c,d]，访问 b。MTF 支付位置 3 后把 b 移到头部；势只需检查 b 与它越过的 c,a 两对，以及 $A$ 同步操作造成的相邻次序变化，未涉及元素对的逆序状态不变。

标准证明取势 $Phi=2I$，$I$ 是两列表之间逆序对数。若访问元素前，MTF 中在它前面但 $A$ 中在它后面的元素有 $x$ 个，MTF 移到头部会消去或新增的逆序可用 $x$ 与两列表位置关系表示，最终得到每次摊还成本至多 $2$ 倍 $A$ 成本加其付费交换项。

免费交换模型只允许刚访问元素向前移动；任意其他重排要逐相邻交换计费。若实现允许一次免费把任意元素搬动，竞争比证明比较的已不是经典 List Update 问题。

参考资料

• Daniel Sleator, Robert Tarjan, Amortized Efficiency of List Update and Paging Rules, CACM, 1985.
• Allan Borodin, Ran El-Yaniv, Online Computation and Competitive Analysis, list update chapter.