【算法导论】 第十二课 跳跃表
本节课介绍了一种全新的数据结构——跳跃表
跳跃表是一种简单又有趣的动态搜索数据结构，其主要优点在于其易于实现，而且很好的保证了其具有高效的性能，即2*O（lgn）的搜索性能
在此之前我想首先谈谈链表，链表的优点在于其插入和删除只需要常数项的时间（加上查找该元素需要额外的O（n）时间），但是其查找效率只有O（n），这里顺带补充一下链表类的问题，以下先给出两个BAT公司面试时热衷于考的两个链表经典问题：
1.如何快速查找单向链表倒数第m个元素
2.如何快速判断一个单向链表是否存在环
对于链表类问题，其核心思想不外乎两点，1是开双指针（甚至多指针），2是开双链表（甚至多链表），其实以上两个问题开双指针便能巧妙地解决，第一个问题，先开一个指针走m步，然后再开一个指针同步走，当前一个指针走到链表末端时，后一个指针就正好指向倒数第m个元素了，第二个问题，开一个快指针和一个慢指针，快指针每次移动两步，慢指针每次移动一步，如果存在环，那么快指针一定会追到慢指针，可以想象两个人在操场赛跑，快的人跑了很久之后会超慢的人一圈。
接下来我们继续谈跳跃表，其实跳跃表用到的就是第二个思路，开双链表甚至多个链表
首先考虑建立两个链表L1和L2，L1为快表，即只保存部分元素，L2为慢表保存全部元素，注意，以下提到的链表均为排好序的链表
那么问题来了？
如何建表L1和 L2呢？L2无疑是一条包含所有结点的单向链表，那么L1应该设置多少个结点最为合理呢，直观上感受L1应该是均匀分布最好，那么是以怎样的密度分布最合适呢？
什么？sqrt（n）还不过瘾？
那么我们还能做怎样的优化呢？答案是加更多的链表，我们看看三条链表应是多少,直觉告诉我们是3*n的1/3次方
其实，可以证明k条链表的时候为k*n的1/k次方
因为n是常数，那么k多大比较合适呢？lgn！ 让我们看看k取lgn的时候为多少，即lgn*n^(1/lgn)为多少，即求lgn*n^logn（2），还记得我们计算递归时间复杂度时的换底公式吗？这里n^logn(2)即2^logn(n)即2^1，即2，所以整个时间复杂度为2*lgn，这是一个非常好的性能。
这种情况下的跳跃表称为理想跳跃表，每一层数量减少一半，总共lgn层链表，从最上级链表开始搜，搜不到就向下，最多下logn层，每层最多搜2个元素，所以搜索复杂度为O（2lgn）
那么问题又来了，如何动态维护这样一个跳跃表呢？
先看删除功能,删除功能只要从上级链表搜到之后，就可以直接删除，并向下将所有链表的该结点都删除，这个比较简单，那么插入呢？
1.保持每段之间的理想距离，如果距离过大，就从中间分割，然后将中点上升一层结点
这个方法从直观上看非常巧妙，但是实行起来却有一定难度，因为你必须实时记录每一段的长度
2.采用我们最喜欢的随机化算法，抛硬币 如果正面，就把这个结点提升一个level（即把该结点也加入上一级的链表中），再抛硬币（看是否持续提升level），因为两个相邻链表的长度之比为1:2，而硬币出正面的概率也是50%，事实证明这样做是可行的，这里值得一提的是，老师在这节课发了两个硬币给同学，一个利用抛硬币产生随机数，一个利用抛硬币决定当前插入结点是否需要提升level，在课堂上直接做起了实验，整个课程氛围也很好，也让同学们都对该算法有了直观的理解，这一种教学方式很值得借鉴
在课堂上，通过实验表明算法2似乎在平均情况下可以得到一个很好的跳跃表，其实不仅仅是平均情况可以得到一个好的跳跃表，在绝大多数情况都可以得到一个好的跳跃表.
可以证明，得到一个好的跳跃表的概率P>=1-O(1/n^a) 这里a是一个介于0到1的参数，与n有关，在课堂的最后，老师花了尽20分钟的时间来证明，具体证明方式我们这里略过（其实是我根本没看懂其证明过程 逃~~）
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
