AI_第一部分 数据结构与算法（15.跳表算法）

第四阶段我们进行深度学习(AI)，本部分（第一部分）主要是对底层的数据结构与算法部分进行详尽的讲解，通过本部分的学习主要达到以下两方面的效果：

1.对开发中常见的算法能应用自如，让你在跳槽找工作中“算法题”不再是阻碍你“钱途”的拦路虎。

2.我们不需要调参数的调参攻城狮，我们要做正真的自己的AI模型。

3.本部分预计40篇左右。

hello,大家好，今天我们来聊一个有点烧脑的数据结构--跳表，what? 跳表是个什么鬼，且听我慢慢道来。这里先给大家说一下，今天的算法不强求大家一定能自己完全写出来，但是整个思路得非常清晰

还记得我们上讲说过的二分查找算法吗，ok 你若还不是很清楚那建议你在看一下上一篇的文章，跳表：就是对链表稍加改造，就可以支持类似“二分”的查找算法。我们把改造之后的数据结构叫作跳表（Skip list）。

第一、如何理解跳表

对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是 O(n)。 那怎么来提高查找效率呢？如果像图中那样，对链表建立一级“索引”，查找起来是不是就会更快一些呢？每两个结点提取一个结点到上一级，我们把抽出来的那一级叫作索引或索引层。你可以看我画的图。图中的 down 表示 down 指针，指向下一级结点。

第二、跳表的数据结构实现

如何从代码的层面来实现跳表呢？我们先看一张图片：

通过图片我们能很清楚的看到：每个节点都是有多个指针的，当然这个指针数的多少与构建的索引的层数是有关系的，最低层是包含所有的数据结点的。（其实质也是用空间换取时间的一种操作）。

第三、跳表查询的效率

这个时间复杂度的分析方法比较难想到。我把问题分解一下，先来看这样一个问题，如果链表里有 n 个结点，会有多少级索引呢？

按照我们刚才讲的，每两个结点会抽出一个结点作为上一级索引的结点，那第一级索引的结点个数大约就是 n/2，第二级索引的结点个数大约就是 n/4，第三级索引的结点个数大约就是 n/8，依次类推，也就是说，第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2，那第 k级索引结点的个数就是 n/(2k)。假设索引有 h 级，最高级的索引有 2 个结点。通过上面的公式，我们可以得到 n/(2h)=2，从而求得 h=log2n-1。如果包含原始链表这一层，整个跳表的高度就是 log2n。我们在跳表中查询某个数据的时候，如果每一层都要遍历 m 个结点，那在跳表中查询一个数据的时间复杂度就是 O(m*logn)。那这个 m 的值是多少呢？按照前面这种索引结构，我们每一级索引都最多只需要遍历 3 个结点，也就是说 m=3，为什么是 3 呢？我来解释一下。

假设我们要查找的数据是 x，在第 k 级索引中，我们遍历到 y 结点之后，发现 x 大于 y，小于后面的结点 z，所以我们通过 y 的 down 指针，从第 k 级索引下降到第 k-1 级索引。在第 k-1 级索引中，y 和 z 之间只有 3 个结点（包含 y和 z），所以，我们在 K-1 级索引中最多只需要遍历 3 个结点，依次类推，每一级索引都最多只需要遍历 3 个结点。

通过上面的分析，我们得到 m=3，所以在跳表中查询任意数据的时间复杂度就是 O(logn)。这个查找的时间复杂度跟二分查找是一样的。换句话说，我们其实是基于单链表实现了二分查找，是不是很神奇？不过，天下没有免费的午

餐，这种查询效率的提升，前提是建立了很多级索引，用空间换时间的设计思路。

第四、跳表的代码实现（python版本）

由于本篇的代码较多，不便于放于文中，如果感兴趣，可以通过我提供的链接获取。

好的，本期我们对于跳表算法就算就说完了，如果有问题可以进行留言。

由于代码仓库出现一些小问题，后续后把代码传上去的。

有小伙伴在后台留言，说能不能推一些关于python面试方面的资料呢，这个已近在考虑之中了，很快就会上线第一季的，敬请期待哈