- 自组织表：
定义两种操作
l n个元素的列表L，访问（可能是查找，也可以是其他操作）元素x的代价与元素在列表中的位置有关（从表头到x的距离）。
l 元素在L中的位置可以通过交换相邻的元素来改变，而这个操作的代价为O(1)。
如果考虑用户的访问可能是一系列的，而且一个元素被访问后，再次被访问的概率会增大，因此考虑对一个元素访问后将该元素和其前驱的元素交换（代价为O(1)），从而减少其下次访问的代价。
1.1. 一个操作序列，每次只发送一次操作请求。
在线算法（online）：必须立即完成这步操作，而不管之后的操作是什么（即不能预知后续操作）。
离线算法（offline）：离线算法可以假设可以预读整个序列，从而可以对整个操作序列做优化。
不管在线、离线算法，其目标都是使得对整个操作序列的总的访问代价最小。
1.2. 复杂度分析
最坏情况分析。
用在线算法使用自组织表，对手每次都可能让我们访问最后一个元素，因此最坏时间为O(n*|S|)，即表长乘操作序列的个数。
平均情况分析。最坏情况无法避免，因此考虑平均情况。
元素x被访问的概率为P(x)（这相当于离线算法）。则对于操作序列，期望的代价为：
每个元素被访问的概率与其位置乘积的和。
因此最小期望为：把元素按访问的概率从大到小排序。因此记录元素被访问的次数，并按访问次数递减的方式排序元素（访问次数大于前驱的访问次数时，进行交换）。因此对于元素x的操作，代价最多为2*rank(x)，因为访问需要rank(x),交换可能需要rank(x)。
思想：前移思想。
1.3. 应用：
这样处理，对于搜索的“流行词”可能会有比较好的反应，因为在一个时期，流行词被搜索的次数会增加，而一旦过了流行期间，其位置可能就被新的流行词替代了。这对于操作序列S的局部反映非常好。
对于高速缓存等其他情况下也可能用到。
- 竞争分析
一个在线算法A是a竞争的:如果存在一个常数k，满足对于任何的操作序列S，满足
CA（S）<=a*Copt(S) + k
即，算法A对S的操作代价不大于其最优的离线算法乘上a，再加k。
Copt（S），也即是如果知道所有操作序列，可以做到的最好的代价。
对a的限定不依赖于任何输入，也不依赖于任何概率假设。
2.1. 对于自组织表MTF（Move to front，移前启发式算法：访问一个元素后，就把元素移动到开头）定理是4竞争的。（即便对手总是访问最后一个元素。）
证明：
l 定义
Li为MTF算法中第i次操作后的表状态。
Li*为最优算法（最好的离线算法）第i次操作后的表状态。
Ci为MTF算法中第i次操作的代价，即x在L(i-1）中位置的2倍。
Ci为最优算法的第i次操作的代价，即x在L(i-1)中位置加上ti(最优表需要交换的次数)。
对于两个不同的代价，使用平摊分析的势能法来确定这两种代价的差距。
l 思路：
定义势能函数f为Li到实数R的映射
f(Li)=2*|一个集合|，即为一个集合元素个数的2倍。
这个集合为{(x,y)|如果在Li集合中x位置小于y，但在Li*集合中y位置小于x}。
由于Li中为最优的，因此Li为有序的。这个集合相当于Li相对于Li*元素定义的顺序的逆序对的数量。
因此
f(Li)=2*(Li的逆序对)。
l f的性质：
f（Li）>=0;
f(L0)=0,如果L0，即初始状态和最优序列L0*相同。
l 一次修改操作，f的值怎么变化，也即一次相邻对换逆序对怎么变化，由排列性质，逆序对增加或减少1，因此势能函数的值的变化为+2或-2。
2.2. 当第i次操作要访问的元素为x时，会发生什么？
根据x在Li和Li*中的位置，将Li中的元素分为四个集合。
A={y| y为Li中的元素，在Li中y在x前面，且在Li*中y在x前面}
B={y| y为Li中的元素，在Li中y在x前面，且在Li*中y在x后面}
C={y| y为Li中的元素，在Li中y在x后面，且在Li*中y在x前面}
D={y| y为Li中的元素，在Li中y在x后面，且在Li*中y在x后面}
直观上：
A与B并集表示Li中小于x的元素集合，C与D的并集表示Li中大于x的元素集合；
A与C并集表示Li中小于x的元素集合，B与D的并集表示Li中大于x的元素集合。
定义：
r=rankLi(x)，即x在Li中的位置。
r=rankLi(x)，即x在Li*中的位置。
由此可得
A,B,C,D的关系还可得
r=|A|+|B|+1，即A，B元素的个数和加1。
r*=|A|+|C|+1，即A，C元素的个数和加1。
2.2.1. 当MIF方式访问后，将x移动到最开头，增加的逆序数为A集合的势（由f(Li)定义的函数），但是会减少B集合势那么多个逆序数。
最优算法方式，则只最多和前驱的元素交换，因此最多增加一个逆序，或减少一个逆序。
从而势能函数的变化量
f(Li)-f(Li-1)<=2(|A|-|B|+ti) （ti为最优表在第i次操作时，交换次数）
由势能方法分析
平摊代价与实际代价之间的关系：第i次操作
ci^=ci+f(Li)-f(Li-1)<=2r+2(|A|-|B|+ti)
=2r+2(|A|-r+|A|+1+ti)——————————————————-(由r定义替换|B|)
=4|A|+2+2*ti
<=4(r-1)+2-2ti=4(r+ti)-2(1+ti)——————————（由r定义，则r*>=|A|+1）
<=4(r+1)—————————————（由ti为正负1则1+ti>=0）
=4ci————————————————————（由c*定义）
从而MTF第i次的平摊代价最多为相应的最优代价的4倍。
从而MTF总的代价为各次代价的和。
Cmtf（S）=c1+…+Cn
=c1^+f(L0)-f(L1)+….+cn^+f(Ln-1)-f(Ln)
=c1^+…+cn^ + f(L0)-f(Ln)
<=4(c1+…+cn*)———————————（由刚才的结论，第i次的平摊代价上限，以及L0的势为0，且f(Ln)>=0）.
=4*Copt(S)。
从而MTF为4竞争的。
2.3. 对于竞争分析
l 如果数据用链表表示，则从x位置移动到表头的操作只需要常数，因此可以忽略其代价，这时可以证明相应的MTF则为2竞争的。
l 如果表的开始的势不为0，即L0和L0不想等，比如有可能已经运行过一段时间了。这时候L0的最差情况为和L0比是反序的，这样逆序为n个元素的逆序，为O(n^2).
这时候Cmtf（S）<=4*Copt(S)+O(n^2)。
如果n的规模相对于S的次数变化不是太大，因此如果操作序列S中的操作为很大时，上式中的O(n^2)也是常量级别的，因此也是4竞争的。
2.4. 如果不是忽略置换的代价，而是一个常数级别的，如3，则相应的结果将改变竞争的常数，常数将不再是4倍。
————————————————
版权声明：本文为CSDN博主「onyheart」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/onyheart/article/details/16331219
