List L of n elems
Operation Access(x),costs rank(x) = distace of x from head of L
L can be reorder by transposing adjcent elements ,cost = 1
Ex
L - > (12) ->(3)->(50)->(14)->(17)->(4)
------------50----3
------------trans-------cost = 4
------------cost 1------for access
A sequence S of operations is provided one at a time for each operation ,for each op an online algorithm must execute the operation immediately
may see all of S in advance
Always access tail elems of L
\(C_A(S)=\Omega(|S|n)\) Worst case
suppose elem x is accessed with prob P(x)
\(E[C_A(S)]=\sum_{x}P(x)*rank(x)\)
Which is minimized when L sorted in decreasing order with respect to P
Heuristic(启发)：Keep account of #times each elem is accessed and maintain lis in order of decreassing count
Practice: "Move - to front" Heuristic
After accessing x move x to head of list,using transposes Cost = 2*rank(x). (Access ,transposes)
Respons well is locality in S
An on-line is \(\alpha\)-competitive
if \(\exists\)const k for any Seq S of ops
\(C_A(S)<=\alpha*C_{OPT}(S)+k\) (Opt is the optimal off-line algorithm,"God‘s alg")
Proof:
Let\(L_i\) be MTF‘s list after i-th access
‘\(L_i^*\)‘ OPT‘s
Let \(C_i\) = MTF cost for i-th op
= 2*rank(\(L_{i-1}(x)\)) if it access x
\(C_i^{ *}\) = OPT‘s cost for i-th op
= $ rank_{ L_{i-1}} (x)+t_i$. if opt forms \(t_i\) transposes
Ddefine potential function \(\phi\) {\(L_i\)}->R by
\(\Phi(L_i)\)=2*|{x,y} , \(x\prec_{L_i}y\) and \(y\prec_{L_i^ * }x\) }|(集合的势就是集合的元素有多少) \(\prec\) 代表优先
? = 2#inversions
Ex:
\(L_i\) -> (E) ->(C)->(A)->(D)->(B)
\(L_i^ *\) ->(C)->(A)->(B)->(D)->(E)
\(\Phi(L_i)\) = 2*|{(E,C),(E,A),(E,D),(E,B),(B,D)}|=10
NOTE:
\(\Phi(L_i)\) >=0\(\forall\)
\(\Phi(L_0)\)=0 if MTF and OPT start with same list
How much does \(\Phi\) change from 1 tranposes
transposes creates or destroy one inversion
\(\Delta\Phi = \pm2\)
What happens when op i access x ?
Define:
A = {\(y\in L{i-1},y \prec _{L_{i-1}}x \ and\ y \prec _{L_{i-1}^ *} x\)}
B = {\(y\in L{i-1},y \prec _{L_{i-1}}x \ and\ y \succ _{L_{i-1}^ *}\)x}
C = {\(y\in L{i-1},y \succ _{L_{i-1}}x \ and\ y \prec _{L_{i-1}^ *}x\)}
D = {\(y\in L{i-1},y \succ _{L_{i-1}}x \ and\ y \succ _{L_{i-1}^ *}x\)}
\(L_{i-1}\)
<---------------------------
|------A\(\cup\) B----------------|x|------C\(\cup\) D--------|
? r = \(rank_{L_{i-1}}(x)\)
$L_{i-1}^ * $
|----A\(\cup\) C---x|---------------------- B\(\cup\) D-------|
? $r^ * $= \(rank_{L_{i-1}^{ * }}(x)\)
we have
r = |A| + |B| + 1
\(r^*\) = |A| + |C| + 1
When MTF moves x to front ,it creates |A| inverstions and destroy |B| inversinos
Each transpose by OPT create <= 1 inversion (\(t_i\) times)
Thus
\(\Phi(L_i)-\Phi(L_{i-1})<=2(|A|-|B|+t_i)\)
\(\hat{c_i}=c_i+\Phi(L_i)-\Phi(L_{i-1}) \\ <= 2*r + 2(|A|-|B|+t_i)\\ = 2*r+2(|A|-(r-1-|A|)+t_i) \quad since \ r = |A|+|B| + 1 \\ =2*r+4*|A|-2*r+2+3*t_i \\ = 4|A|+2+2t_i\\ <=4*(r^* + t_i) \quad since \ r^* = |A|+|C|+1 >=|A|+1 \\ = c_i^ *\)
Thus \(C_MTF(S) = \sum_{i=1} c_i \\ = \sum_{i=1}\hat{c_i}+\Phi(L_i)-\Phi(L_{i-1}) \\ = \sum_{i=1}4_i c^*+\Phi(L_0)-\Phi(L_S)(=0,>0)\\ <= 4 C_{OPT}(S)\)
If we count transpose that move x to front of L as "free"
modeles splicing(拆分) x in and out of L in constant time and MTF is 2-competitve
What if $L_0\neq L_0^* $ Then. \(\Phi(L_0)\) Might be \(\Theta(n^2)\)C(n-1,2)
Thus
\(C_MTF(S)<= 4 C_{OPT}(S)+\Theta(n^2)\)
is still 4 - comp. since \(n^2\) is constant as the size of S goes to infinity. |S|->∞
原文：https://www.cnblogs.com/shcnee/p/13062626.html