今天看了MIT算法导论公开课之第14课 竞争性分析、自组织表 所以就对所学到的知识作一下总结！
自组织表
定义：含有n个元素的链表L
用户操作：
a.访问其中的元素Access(x)。
b.查找元素的位置Rank(x)（从表头到x的距离）。
c.置换相邻的元素reorded()。
算法操作：
链表L可以通过交换相邻元素调整元素顺序，且置换代价为1。
（如果考虑用户的访问可能是一系列的，而且一个元素被访问后，再次被访问的概率会增大，因此考虑对一个元素访问后将该元素和其前驱的元素交换（代价为O(1)），从而减少其下次访问的代价。）
举个栗子：
在线算法与离线算法
1.在线算法
必须立即完成这步操作，而不管之后的操作是什么（即不能预知后续操作）
2.离线算法
离线算法可以假设可以预读整个序列，从而可以对整个操作序列做优化。
对比一下：可以看出两者的区别在于是不是知道后续的操作.
可以举个栗子说明一下：
我们经常玩的游戏俄罗斯方块，在玩的时候我们不能预知下一个出现的方块是什么，所以必须先完成当前的这个方块的操作。而离线方法，相当于你知道了后续所有方块，你就可以根据后续的方块来进行游戏操作了。
画个重点：不论是在线算法还是离线算法，其目标都是使得对整个操作序列的总的访问代价最小。
复杂度分析
思想：MTF （前移思想）
竞争分析
公式解析：即算法A对S的操作代价不大于其最优的离线算法乘上a，再加k（K为常数）。
Copt（S），即是如果知道所有操作序列，可以做到的最好的代价。
对a的限定不依赖于任何输入，也不依赖于任何概率假设。
自组织表的MTF（Move-to-front）算法为四竞争的证明
今天是霜降啦~所以也要是元气满满 活力的一天啦~
来自不想学习 想食补的小李啦！
finally
鸣谢一下参考：MIT算法导论公开课之第14课 竞争性分析、自组织表 - rye_whiskey的博客 - CSDN博客
https://blog.csdn.net/yalishadaa/article/details/54945362
网友评论