竞争性分析自组织表

我不是女神ヾ 2022-07-12 03:36 166阅读 0赞

1.        自组织表：

定义两种操作

l  n个元素的列表L，访问（可能是查找，也可以是其他操作）元素x的代价与元素在列表中的位置有关（从表头到x的距离）。

l  元素在L中的位置可以通过交换相邻的元素来改变，而这个操作的代价为O(1)。

**如果考虑用户的访问可能是一系列的，而且一个元素被访问后，再次被访问的概率会增大，因此考虑对一个元素访问后将该元素和其前驱的元素交换（代价为O(1)），从而减少其下次访问的代价**。

1.1.       一个操作序列，每次只发送一次操作请求。

**在线[算法][Link 1]（online）**：必须立即完成这步操作，而不管之后的操作是什么（即不能预知后续操作）。

**离线算法（offline）**：离线算法可以假设可以预读**整个序列**，从而可以对整个操作序列做优化。

不管在线、离线算法，其目标都是使得对整个操作序列的总的访问代价最小。

1.2.       复杂度分析

最坏情况分析。

用在线算法使用自组织表，对手每次都可能让我们访问最后一个元素，因此最坏时间为O(n\*|S|)，即表长乘操作序列的个数。

平均情况分析。最坏情况无法避免，因此考虑平均情况。

元素x被访问的概率为P(x)（这相当于离线算法）。则对于操作序列，期望的代价为：

每个元素被访问的概率与其位置乘积的和。

因此最小期望为：把元素按访问的概率从大到小排序。因此记录元素被访问的次数，并按访问次数递减的方式排序元素（访问次数大于前驱的访问次数时，进行交换）。因此对于元素x的操作，代价最多为2\*rank(x)，因为访问**需要**rank(x),交换**可能需要**rank(x)。

思想：前移思想。

**1.3.       应用：**

**这样处理，对于搜索的“流行词”可能会有比较好的反应，因为在一个时期，流行词被搜索的次数会增加，而一旦过了流行期间，其位置可能就被新的流行词替代了。这对于操作序列S的局部反映非常好。**

**对于高速缓存等其他情况下也可能用到。**

2.        竞争分析

一个**在线算法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)<=2\*r+2\*(|A|-|B|+ti)

=2\*r+2\*(|A|-r+|A|+1+ti)-------------------------------------(由r定义替换|B|)

=4|A|+2+2\*ti

<=4\*(r\*-1)+2-2\*ti=4\*(r\*+ti)-2(1+ti)--------------------（由r\*定义，则r\*>=|A|+1）

<=4\*(r\*+1)--------------------------（由ti为正负1则1+ti>=0）

=4\*ci\*----------------------------------------（由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倍。

原文地址:http://blog.csdn.net/onyheart/article/details/16331219

[Link 1]: http://lib.csdn.net/base/datastructure

竞争性分析自组织表

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关堆表和索引组织表区别

相关 mysql堆表和索引组织_堆表与索引组织表

相关培育自组织团队

相关 SOM自组织神经网络

相关竞争性分析自组织表

相关 Oracle dump索引组织表

相关 Mysql聚集索引和非聚集索引(堆组织表和索引组织表)

相关敏捷中的自组织团队

相关 EBS组织表

相关第二章用表组织数据