（移至前段自组织列表的竞争分析）自组织列表是n个元素的链表，_

（移至前段自组织列表的竞争分析）自组织列表是n个元素的链表，每个元素有一个唯一的关键字，当我们在列表中搜索元素时，需要给定一个关键字，我们搜索的是具有这个关键字的元素。

一个自组织列表有两个重要的性质：

1.为了在一个列表中查找一个元素，我们必须从表头开始遍历列表，直到遇到具有给定关键字的元素位置，如果此元素是列表的第k个元素，则查找代价为k。

2.我们可以在任意一个操作后根据给定规则重排列表元素，产生一定的代价。我们可以使用任何我们喜欢的启发式策略来决定如何重排列表。

假定从一个给定的n个元素的列表开始，并且给定了一个访问序列——关键字搜索序列 $\sigma=<\sigma_{1},\sigma_{2},...,\sigma_{m}>$ 。序列的代价是序列中单个访问的代价之和。

在多种可能的列表重排方法中，本问题关注相邻元素转置操作——交换相邻元素在列表中的位置，一次转置的代价为单位时间，你可以用势函数证明：针对移至前端列表的重排问题，一种特定的启发式策略的代价最坏情况也不会超过任何其他启发式策略代价的4倍，即使其他启发式策略预先知道访问序列！我们称这种分析为竞争分析。

对于一个启发式策略H和列表的一个给定的初始顺序，我们将序列 $\sigma$ 的访问代价记为C_H( $\sigma$ )。令m表示 $\sigma$ 中访问的数量。

a.证明：若启发式策略H预先不知道访问序列，那么利用H来处理访问序列 $\sigma$ 的最坏情况代价为C_H( $\sigma$ )= $\Omega(mn)$ 。

当使用移至前端启发式策略时，搜索到元素x后，我们将x移动到列表的第一个位置（即列表的前端）。

令rank_L(x)表示元素x在列表中L中的符号，即x在L中的位置。例如，若x是L中的第4个元素，那么rank_L(x)=4,。令ci表示用移至前端策略处理访问 $\sigma_{i}$ 的代价，包括在列表中查找元素的代价和通过一系列的相邻元素转置操作将其移至列表前端的代价。

b.证明：如果 $\sigma_{i}$ 使用移至前端策略在L中访问元素x，则c_i=2*rank_L(x)-1。

现在我们比较移至前端策略与其他任何按照上述两个性质处理访问序列的启发式策略H。策略H可能按任何想用的方式转置列表中的元素，它甚至可能预先知道整个访问序列。

令L_i表示使用移至前端策略处理访问 $\sigma_{i}$ 后得到的列表，L_i*表示使用策略H后得到的列表。我们用ci表示移动前端策略的代价，c_i*表示策略H的代价。假定策略H在处理访问 $\sigma_{i}$ 时执行t_i*次转置。

c.在（b）中，你证明了c_i=2*rank_Li-1(x)-1。现在证明：c_i*=2*rank_L*_i-1(x)-t_i*。

我们定义逆序关系（inversion）：L_i中一对元素y和z,在L_i中y在z之前，在L_i*中z在y之前。假定处理完访问序列 $<\sigma_{1},\sigma_{2},...,\sigma_{i}>$ ，Li中有qi个逆序关系。然后我们定义一个势函数 $\Phi$ ，将Li映射到实数 $\Phi(L_{i})=2q_{i}$ 。例如Li有元素<e,c,a,d,b>，而Li*有元素<c,a,b,d,e>，那么L_i有5个逆序((e,c),(e,a),(e,d),(e,b),(d,b))，因此 $\Phi(L_{i})=10$ 。观察到对所有i，都有