自组织列表|集合1（简介）

排序链表的最坏搜索时间是O（n）。使用平衡二叉搜索树，我们可以在与根进行一次比较后跳过几乎一半的节点。对于排序数组，我们可以随机访问，并且可以对数组应用二进制搜索。

让搜索链接列表更快的一个想法是 跳跃表 .另一个想法是 将更频繁接触的物品放在靠近头部的位置。 .有两种可能。离线（我们提前知道完整的搜索顺序）和在线（我们不知道搜索顺序）。 在离线情况下，我们可以根据搜索频率的降低来放置节点（首先放置具有最大搜索计数的元素）。在许多实际应用中，可能很难提前获得搜索序列。A. 自组织列表 根据已完成的搜索对其节点重新排序。其想法是使用参考位置（在一个典型的数据库中，80%的访问是对20%的项目的访问）。以下是自组织列表使用的不同策略。

1) 前移法 ：搜索的任何节点都将移动到前面。这种策略很容易实现，但它可能会过度奖励不常访问的项目，因为它总是将项目移动到前面。

2) 计数法 ：每个节点存储搜索次数的计数。节点按递减计数排序。这种策略需要额外的空间来存储计数。

3) 转置法 ：搜索的任何节点都将与前一个节点交换。与移动到前端不同，这种方法不能快速适应不断变化的访问模式。

竞争分析： 所有方法的最坏情况时间复杂度都是O（n）。在最坏的情况下，搜索的元素总是列表中的最后一个元素。对于 平均案例分析 ，我们需要搜索序列的概率分布，这是很多次都不可用的。 对于上述在线策略和算法，我们有一种完全不同的分析方法，称为 竞争分析 其中，在线算法的性能与最佳离线算法（可以提前查看请求序列）的性能进行比较。竞争分析被用于许多实用算法，如缓存、磁盘分页和高性能计算机。竞争分析最好的一点是，我们不需要对投入的概率分布做任何假设。Move to front方法是4-competitive的，这意味着它的运算量永远不会超过离线算法的4倍（参见 麻省理工学院视频讲座 （作为证据）。

我们将很快讨论视频讲座中给出的分析的实现和证明。

参考资料： http://en.wikipedia.org/wiki/Self-organizing_list 麻省理工学院视频讲座 http://www.eecs.yorku.ca/course_archive/2003-04/F/2011/2011A/DatStr_071_SOLists.pdf http://en.wikipedia.org/wiki/Competitive_analysis_（在线算法）

本文由 阿比拉蒂 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论