自组织表

先来理解两个概念

在线算法与离线算法

在线算法(也成为线上算法):是一个处理数据的一种方式,他不要求建立数据结构的时候所有数据源全部就绪,在不断获取数据源的时候,插入到数据结构之中。

离线算法:与在线算法正好相反,他在一开始就获取了所有的数据源,并且,他能够通过一些分析,去优化整个数据结构,比如链表就将最频繁的节点放置到链表的前列。

并且,有些算法他会同时拥有在线和离线两个版本的实现,并具有不同的特性。通常来讲,离线算法将会拥有更好的性能。

书中介绍了一种在线算法,对链表 l 尝试访问元素 x 的时候,将 x 不断的进行置换,直到到表头元素,这种算法对某个区域时间内某个元素突然变得热门会很有效。我自己也想到了一种在线算法。访问元素 x 的时候,将 x 与他的前置元素进行置换,然后返回。这样可以保证在一段时间后的访问之后,整体会以访问频率降序的方式分布,并且非常简单。

竞争性分析

定义

如果满足以下公式 我们称:算法 a 与 α 是竞争的

如果存在一个常数 K 满足对于任意序列 S C a(S) <= α _ C opt(S) + k // opt 的含义是最优算法,又称上帝算法 语义化描述: 算法 a 操作序列 s 的代价 小于等于 因子 α _ 最优算法操作序列 S 的代价 加上 一个常数 含义: 大致含义就是这算法的上限和最优算法的差距。其中差距多少就要调整 α 的值了,如果假设 α 是 2,那么可以认为这个算法的代价大致是最优算法的两倍。