跳过列表|集合1（简介）

我们能在比O（n）时间更好的时间内搜索排序的链表吗？ 排序链表的最坏情况下的搜索时间是O（n），因为我们只能线性遍历链表，在搜索时不能跳过节点。对于平衡二叉搜索树，在与根进行一次比较后，我们跳过了几乎一半的节点。对于排序数组，我们可以随机访问，并且可以对数组应用二进制搜索。

我们是否可以增加已排序的链表以加快搜索速度？答案是 跳跃表 这个想法很简单，我们创建了多个层，这样我们就可以跳过一些节点。请参见以下包含16个节点和两个层的示例列表。上层用作“快速车道”，仅连接主要外部车站，下层用作“普通车道”，连接每个车站。假设我们想要搜索50，我们从“快车道”的第一个节点开始，继续在“快车道”上移动，直到找到下一个大于50的节点。一旦我们在“快速车道”上找到这样一个节点（30是下面示例中的节点），我们就使用该节点的指针移动到“正常车道”，并在“正常车道”上线性搜索50。在下面的例子中，我们从“普通车道”上的30开始，通过线性搜索，我们找到50。

两层的时间复杂度是多少？ 最坏情况下的时间复杂度是“快速车道”上的节点数加上“正常车道”的一段中的节点数（一段是两个“快速车道”节点之间的“正常车道”节点数）。如果我们在“普通车道”上有n个节点，&Sqrt；n（n个节点的平方根）在“快速车道”上，我们平均划分“正常车道”，那么将有&Sqrt；在“正常车道”的每段中有n个节点&Sqrt；n实际上是两层的最佳分割。通过这种安排，搜索所遍历的节点数将为O（&Sqrt；n）。因此，有了O（&Sqrt；n）额外的空间，我们可以将时间复杂度降低到O（&Sqrt；n）。

我们能做得更好吗？ 通过添加更多层，可以进一步降低跳过列表的时间复杂度。事实上，搜索、插入和删除的时间复杂度在平均情况下可以变成O（Logn），并且有O（n）个额外空间。我们很快就会在跳过列表上发布更多帖子。

工具书类 麻省理工学院跳过列表视频讲座 http://en.wikipedia.org/wiki/Skip_list

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。