下载文档原格式
跳跃表原理和实现跳跃表是一种搜索算法，它可以在O（log n）时间内进行搜索，可以在不同程度上提高搜索效率。
跳跃表是一种实现了有序数据集在O(log n)时间内搜索的数据结构，它的设计思想和二叉搜索树相似。
它的性能比二叉搜索树要好，因为跳跃表可以在更短的时间内查找结果，但是它的构造和维护比二叉搜索树要复杂，在构建跳跃表的时候要做到层级和索引的正确性。
跳跃表的典型应用场景在现在的项目中很多，比如计算数据和模型之间的关系，检索数据，查找范围等等。
跳跃表的原理很简单，它由一系列有序链表组成，每个链表可以分成多个层次，每个层次都有相应的索引。
索引指向各自层级中最小的值，这样可以最大程度减少查找时间。
跳跃表也可以支持log n的插入和删除操作，插入和删除的复杂度将取决于层级的正确性。
构建跳跃表的第一步需要在链表中插入某个索引，该索引指向最后一个值，类似于二叉搜索树中的叶子结点。
接下来，可以采用二分搜索的思想，从最后一层开始搜索，直到搜索到小于给定值的最近一层。
对于每一层，都需要计算出该层的最小索引，以及更高层的最小索引，并将其与目标值比较，以确定当前层的结果。
跳跃表的删除操作跟插入类似，首先根据给定值定位到目标所在层，然后移除该值，然后重新构建该层的索引，并删除更新高层层级的索引。
跳跃表也可以进行更新操作，但需要在更新完毕后重新构建索引，以及调整层级，从而让搜索结果更加准确。
跳跃表还有一些其他的应用，比如可以利用跳跃表实现获取某一范围内的值，这也是跳跃表非常有用的应用场景之一。
此外，跳跃表还可以被用于实现排序算法，比如计数排序，以及更多的时间复杂度为O（log n）的应用场景。
总的来说，跳跃表是一种非常有用的数据结构，它比二叉搜索树要快，它的搜索时间复杂度也可以达到O（log n）的水平，在计算性能要求较高的应用场景中，它可以为程序性能提升起到重要作用。
跳跃表的实现也非常复杂，但是如果正确地使用，它可以提供极高的搜索速度。
查找——图⽂翔解SkipList（跳跃表）跳跃表跳跃列表（也称跳表）是⼀种随机化数据结构，基于并联的链表，其效率可⽐拟于⼆叉查找树（对于⼤多数操作须要O(logn)平均时间）。
基本上。
跳跃列表是对有序的链表添加上附加的前进链接，添加是以随机化的⽅式进⾏的。
所以在列表中的查找能够⾼速的跳过部分列表元素，因此得名。
全部操作都以对数随机化的时间进⾏。
例如以下图所看到的。
是⼀个即为简单的跳跃表。
传统意义的单链表是⼀个线性结构。
向有序的链表中插⼊⼀个节点须要O(n)的时间。
查找操作须要O(n)的时间。
假设我们使⽤图中所看到的的跳跃表。
就能够⼤⼤降低降低查找所需时间。
由于我们能够先通过每⼀个节点的最上层的指针先进⾏查找，这样⼦就能跳过⼤部分的节点。
然后再缩减范围，对以下⼀层的指针进⾏查找，若仍未找到，缩⼩范围继续查找。
上⾯基本上就是跳跃表的思想。
每个结点不单单仅仅包括指向下⼀个结点的指针。
可能包括⾮常多个指向兴许结点的指针，这样就能够跳过⼀些不必要的结点，从⽽加快查找、删除等操作。
对于⼀个链表内每⼀个结点包括多少个指向兴许元素的指针，这个过程是通过⼀个随机函数⽣成器得到。
这样⼦就构成了⼀个跳跃表。
构造由图不难理解跳跃表的原理，能够看出。
跳跃表中的⼀个节点是有不同数⽬的后继指针的。
那么问题来了，这详细是怎样实现的？这些节点是怎样构造的？【分析】我们不可能为每⼀种后继指针数⽬的节点分配⼀种⼤⼩类型的节点，那我们就提取共性，看这些节点有何共通之处。
这些节点可看做由两部分构成：数据域、指针域。
数据域包含key-Value，指针域是后继指针的集合。
那怎样在节点中保存后继指针集合呢？⽤⼀个⼆级指针，分配节点的时候指向动态分配的后继指针数组。
这个⽅法似乎可⾏，但问题在于我们的节点也是动态分配的，这种话，在释放节点的时候还须要先释放节点中动态分配的数组。
释放操作⽐較繁琐。
灵光⼀闪！之前本博客中介绍了⼀种称为“零数组”的技术，或许能够帮到我们。
Redis中的跳表date: 2020-10-15 14:58:00updated: 2020-10-19 17:58:00Redis中的跳表redis 数据类型 zset 实现有序集合，底层使⽤的数据结构是跳表。
源码在 src/t_zset.c ⽂件中，相关数据结构的定义在 src/server.h ⽂件中。
(4.0版本)元素有序的时候，如果是数组，可以通过⼆分查找来提速；如果是链表，如何提速？ => 跳表，插⼊/删除/搜索都是O(logn)第⼀层索引 n/2 个节点，第⼆层 n/4 个节点，第三层 n/8，第K层 n/(2^k)假设第K层有2个节点，即 n/(2^k) = 2 => k = log2(n) - 1typedef struct zskiplist {// 头节点，尾节点struct zskiplistNode *header, *tail;// 节点数量unsigned long length;// ⽬前表内节点的最⼤层数int level;} zskiplist;typedef struct zskiplistNode {// member 对象robj *obj;// 分值double score;// 后退指针struct zskiplistNode *backward;// 层struct zskiplistLevel {// 前进指针struct zskiplistNode *forward;// 这个层跨越的节点数量unsigned int span;} level[];} zskiplistNode;1. 跳表 SkipList在 java.util.concurrent.ConcurrentSkipListMap/ConcurrentSkipListSet 类中也有实现查询链表时会从头到尾的遍历链表，最坏的时间复杂度是O(N)，这是⼀次⽐较⼀个值，如果跳着1个元素来进⾏⽐较（⽐较下标为2n+1的元素），那么就相当于⼀次性⽐较2个元素，效率就会提⾼ => 跳表跳表是牺牲空间来换取时间，除了最底层是最原始的数据外，其他的每⼀层，其实都相当于是⼀个索引，最理想的是按照第⼀层1级跳，第⼆层2级跳，第三层4级跳，第四层8级跳。
zset原理zset，即有序集合，是Redis中的一种数据结构，它是将一组成员（member）与每个成员相关联的分数（score）进行关联的一种有序映射。
这种数据结构在实际应用中具有广泛的用途，特别适用于需要排序和范围查询的场景。
本文将从zset的基本原理、使用方法以及应用案例等方面进行介绍。
一、zset的基本原理zset是通过将成员与分数进行映射来实现有序性的。
每个成员都有一个唯一的标识符，称为成员名，而分数则用于对成员进行排序。
zset内部使用一种称为跳跃表（skiplist）的数据结构来实现有序存储和高效的范围查询。
跳跃表是一种类似于链表的数据结构，每个节点包含一个成员和对应的分数，同时还包含了指向其他节点的指针，使得查询和插入操作的时间复杂度为O(logN)。
跳跃表通过层级的方式来提高查询效率，每层都是成员的一个子集，通过跳跃指针可以快速定位到目标节点，从而缩小搜索范围。
二、zset的使用方法zset在Redis中提供了一系列的命令来对有序集合进行操作。
常用的命令包括：- ZADD：向有序集合中添加一个或多个成员，同时指定对应的分数；- ZRANK：返回指定成员在有序集合中的排名，按照分数从小到大排序；- ZRANGE：返回指定排名范围内的成员，按照分数从小到大排序；- ZREM：从有序集合中移除一个或多个成员；- ZSCORE：返回指定成员的分数。
除了上述基本命令外，zset还提供了一些其他功能，如求交集、并集和差集等。
通过这些命令，可以实现对有序集合的增删改查操作，以及对成员进行排序和范围查询等功能。
三、zset的应用案例1. 排行榜：zset常被用于实现排行榜功能。
将用户的得分作为成员的分数，可以通过ZADD命令来更新用户的得分，通过ZRANGE命令来获取排名前几的用户，从而实现排行榜的展示。
2. 帖子排序：在论坛或社交媒体等场景中，可以使用zset来对帖子进行排序。
将帖子的热度或点赞数作为成员的分数，可以通过ZADD命令来更新帖子的热度，通过ZRANGE命令来获取热度最高的帖子。
跳跃表（Skip List）是一种用于快速查找的数据结构，它以链表为基础并添加了多层索引。
跳跃表允许快速地插入、删除和查找元素，同时具有较低的时间复杂度。
跳跃表的基本结构由一个有序链表组成，每个节点包含一个键值对。
为了提高查找效率，跳跃表还在原始链表上添加了若干层索引。
最底层是原始链表，接着是第一级索引，再接着是第二级索引，依此类推，直到顶层索引。
每一层索引都是原始链表的一部分，其中的节点包含指向下一层的指针。
通过这些指针，查找操作可以跳过一些节点，从而加快查找速度。
例如，如果要查找一个特定的键值，可以从顶层索引开始，在每一级索引中根据键值进行比较，并沿着合适的路径向下移动，直到到达最底层索引。
插入和删除操作也很简单高效。
插入操作首先在最底层索引中找到插入位置，然后根据一定的概率随机决定是否在更高层插入相同的节点，从而维持跳跃表的平衡性。
删除操作将要删除的节点从每一层索引中移除，并更新指针，使得不再引用该节点。
跳跃表的时间复杂度为O(log n)，其中n为元素数量。
这使得它在某些场景下比平衡二叉搜索树具有更好的性能，尤其是在无法以平衡树方式维护数据时。
总结来说，跳跃表是一种高效的数据结构，可以实现快速的插入、删除和查找操作。
它的设计简单，实现相对容易，同时具有较低的时间复杂度。
由于其优秀的性能和易于实现的特性，跳跃表在各种应用中都得到了广泛的使用。
跳跃表原理和实现
跳跃表(Skip List)是一种常用的非结构化数据结构，用来实现非关系型数据库中的有序数据插入、删除、查找操作，一般来说跳跃表的时间复杂度比较低，并且比其它有序数据结构表现更优越。
跳跃表的原理其实很简单，就比如我们要从上往下跳，可以直接从中间跳跃过去，从而把跳跃步数减少，所以跳跃表就是从上到下跳跃，从而减少查询步骤，同时也增加索引数据结构的性能。
跳跃表的实现非常简单，它有三个主要组件：一个跳表头节点、一个跳表尾节点及其之间的跳表元素节点，最终形成一个层状的跳表结构，节点的后继指针为每个节点在同一层次上的下一个节点，节点的上下指针为同一节点在上一层和下一层的节点。
其中，每个跳表元素节点包括一个数据域（存放着一个元素）和多个指针域，指针域指向相应的上一层和下一层的跳表元素节点，每个指针域称为一个Level，而且跳表的Level数和元素的Level数是应该是动态的。
向跳表中添加、查找、删除节点的过程，分别如下：
1、添加元素：从跳表头节点开始，遍历跳表每层Level，找到总值大于等于插入元素值的元素时，将目标元素插入到其下一层Level对应的索引表项中，以此
类推，即可完成插入操作
2、删除元素：同插入元素操作，从跳表头元素开始，遍历每一层Level，当找到比目标元素值小的元素时，从此元素相应Level的索引表项中删除该元素，以此类推，即可完成删除操作
3、查找元素：从跳表头元素开始，遍历每一层Level，当查找到等于目标元素值的元素，即可完成查找操作。
所以，通过以上思路，可以很容易实现跳跃表的插入、删除和查找操作。
跳跃表总结引言跳跃表（Skip List）是一种高效的数据结构，用于实现快速查找和插入操作。
跳跃表的设计初衷是为了解决有序链表在查找时的低效性问题。
通过使用随机化的方式，跳跃表可以在保持元素有序性的同时，在平均情况下实现O(log n)的查找和插入操作。
原理跳跃表的核心思想是通过添加多级索引来加速查找操作。
每一级索引都是原始链表的一部分，且不同级别的索引元素存在一定的间隔，使得查找的时间复杂度得以降低。
跳跃表中的每个节点包含一个值和若干个指针，指向同一级别或下一级别的节点。
每个级别的头指针指向该级别的第一个节点。
最底层的链表被视为原始链表，包含所有的元素。
在查找元素时，跳跃表从最高级别的头指针开始，沿着索引指针向右移动，直到找到小于或等于待查找元素的节点或者到达索引指针的末尾。
然后，跳跃表沿着指针向下移动到下一级别，重复上述过程。
最终，在底层链表中，线性搜索找到目标元素。
在插入元素时，首先进行搜索操作以确定将元素插入的位置。
然后，在底层链表中插入新节点，并根据一定的概率随机决定是否在上层插入新节点来维护索引的平衡性。
时间复杂度分析跳跃表通过增加多级索引来加速查找和插入操作。
对于包含n个元素的跳跃表，其高度为O(log n)，每层索引的节点数量约为原始链表节点数量的1/2。
因此，跳跃表的查找和插入操作的平均时间复杂度为O(log n)，具有较好的性能。
优缺点总结跳跃表作为一种高效的数据结构，具有多个优点： - 查找和插入操作的时间复杂度为O(log n)，相对于有序链表的O(n)具有较好的性能。
- 可以动态插入和删除节点，且操作简单高效。
- 空间效率较高，维护索引所需的额外空间相对较小。
然而，跳跃表也存在一些缺点： - 在实现过程中，需要维护索引的平衡性，增加了操作的复杂度。
- 跳跃表相对于其他数据结构来说，实现和理解较为复杂，需要深入了解其原理和实现细节。
应用场景跳跃表在很多实际应用中被广泛使用，特别适用于需要高效查找和插入操作的场景，例如： - 在数据库中用于实现索引结构，加速查询操作。
在excel中，不连续的单元格区域的选择方法在Excel中,不连续的单元格区域通常称为“跳跃表”或“跳跃表区域”。
它们是一种特殊的单元格区域,可以在其中包含多个连续的单元格,而中间插入一些空单元格。
以下是一些选择不连续单元格区域的方法:方法一:使用公式1. 在单元格中输入以下公式:=COUNTIF(A1:A100,">="&B1)2. 选择包含跳跃表的单元格区域,例如A1:B100。
3. 按Enter键。
4. 可以看到计算结果,它表示该单元格区域中跳跃表的行数。
方法二:使用条件格式1. 选择包含跳跃表的单元格区域。
2. 右键单击单元格背景,然后选择“条件格式”。
3. 选择“新建规则”。
4. 在“格式单元格”下,选择“单元格值”。
5. 选择“大于”。
6. 输入公式“=COUNTIF(A1:A100,">="&B1)”。
7. 选择要应用的格式。
8. 单击“确定”。
9. 可以看到效果,单元格A1到A100中的所有大于B1的单元格将应用相同的格式。
方法三:使用选择工具1. 选择包含跳跃表的单元格区域。
2. 右键单击选择工具栏,然后选择“选择所有不连续单元格”。
3. 可以看到所有在跳跃表中的单元格都被选中了。
4. 右键单击这些单元格,然后选择“格式选项”。
5. 在“格式”组中,选择“单元格值”。
6. 选择“大于”。
7. 可以看到效果,所有在跳跃表中的单元格都应用了相同的格式。
这些方法可以帮助您选择不连续的单元格区域,以满足您的需求。
数据结构与算法（c++）——跳跃表（skiplist）今天要介绍⼀个这样的数据结构：1. 单向链接2. 有序保存3. ⽀持添加、删除和检索操作4. 链表的元素查询接*线性时间——跳跃表 Skip List⼀、普通链表对于普通链接来说，越靠前的节点检索的时间花费越低，反之则越⾼。
⽽且，即使我们引⼊复杂算法，其检索的时间花费依然为O(n)。
为了解决长链表结构的检索问题，⼀位名叫William Pugh的⼈于1990年提出了跳跃表结构。
基本思想是——以空间换时间。
⼆、简单跳跃表（Integer结构）跳跃表的结构是多层的，通过从最⾼维度的表进⾏检索再逐渐降低维度从⽽达到对任何元素的检索接*线性时间的⽬的O(logn)。
如图：对节点8的检索⾛红⾊标记的路线，需要4步。
对节点5的检索⾛蓝⾊路线，需要4步。
由此可见，跳跃表本质上是⼀种⽹络布局结构，通过增加检索的维度（层数）来减少链表检索中需要经过的节点数。
理想跳跃表应该具备如下特点：包含有N个元素节点的跳跃表拥有log2N层，并且上层链表包含的节点数恰好等于下层链表节点数的1/2。
但如此严苛的要求在算法上过于复杂。
因此通常的做法是：每次向跳跃表中增加⼀个节点就有50%的随机概率向上层链表增加⼀个跳跃节点，并以此类推。
接下来，我们做如下规范说明：1. 跳跃表的层数，我们称其维度。
⾃顶向下，我们称为降维，反之亦然。
2. 表中，处于不同链表层的相同元素。
我们称为“同位素”。
3. 最底层的链表，即包含了所有元素节点的链表是L1层，或称基础层。
除此以外的所有链表层都称为跳跃层。
以下是代码实现#pragma once#ifndef SKIPLIST_INT_H_#define SKIPLIST_INT_H_#include <cstdlib> /* srand, rand */#include <ctime> /* time */#include <climits> /* INT_MIN *//* 简单跳跃表，它允许简单的插⼊和删除元素，并提供O(logn)的查询时间复杂度。
跳跃表（数据结构）二叉树是我们都非常熟悉的一种数据结构。
它支持包括查找、插入、删除等一系列的操作。
但它有一个致命的弱点，就是当数据的随机性不够时，会导致其树型结构的不平衡，从而直接影响到算法的效率。
跳跃表（Skip List）是1987年才诞生的一种崭新的数据结构，它在进行查找、插入、删除等操作时的期望时间复杂度均为O(logn),有着近乎替代平衡树的本领。
而且最重要的一点，就是它的编程复杂度较同类的AVL树，红黑树等要低得多，这使得其无论是在理解还是在推广性上，都有着十分明显的优势。
跳跃表由多条链构成（S0，S1，S2……，Sh），且满足如下三个条件：（1）每条链必须包含两个特殊元素：+∞ 和 -∞（2）S0包含所有的元素，并且所有链中的元素按照升序排列。
（3）每条链中的元素集合必须包含于序数较小的链的元素集合，即：【基本操作】在对跳跃表有一个初步的认识以后，我们来看一下基于它的几个最基本的操作。
一、查找目的：在跳跃表中查找一个元素x在跳跃表中查找一个元素x，按照如下几个步骤进行：i)从最上层的链（Sh）的开头开始ii)假设当前位置为p，它向右指向的节点为q（p与q不一定相邻），且q的值为y。
将y与x作比较(1) x=y 输出查询成功及相关信息(2) x>y 从p向右移动到q的位置(3) x<y 从p向下移动一格iii) 如果当前位置在最底层的链中（S），且还要往下移动的话，则输出查询失败二、插入目的：向跳跃表中插入一个元素x首先明确，向跳跃表中插入一个元素，相当于在表中插入一列从S中某一位置出发向上的连续一段元素。
有两个参数需要确定，即插入列的位置以及它的“高度”。
关于插入的位置，我们先利用跳跃表的查找功能，找到比x小的最大的数y。
根据跳跃表中所有链均是递增序列的原则，x必然就插在y的后面。
而插入列的“高度”较前者来说显得更加重要，也更加难以确定。
由于它的不确定性，使得不同的决策可能会导致截然不同的算法效率。
为了使插入数据之后，保持该数据结构进行各种操作均为O(logn)复杂度的性质，我们引入随机化算法（Randomized Algorithms）。
我们定义一个随机决策模块，它的大致内容如下：·产生一个0到1的随机数r r ← random()·如果r小于一个常数p，则执行方案A， if r<p then do A否则，执行方案B else do B初始时列高为1。
插入元素时，不停地执行随机决策模块。
如果要求执行的是A操作，则将列的高度加1，并且继续反复执行随机决策模块。
直到第i次，模块要求执行的是B操作，我们结束决策，并向跳跃表中插入一个高度为i的列。
性质1：根据上述决策方法，该列的高度大于等于k的概率为p k-1。
此处有一个地方需要注意，如果得到的i比当前跳跃表的高度h还要大的话，则需要增加新的链，使得跳跃表仍满足先前所提到的条件。
我们来看一个例子：假设当前我们要插入元素“40”，且在执行了随机决策模块后得到高度为4·步骤一：找到表中比40小的最大的数，确定插入位置·步骤二：插入高度为4的列，并维护跳跃表的结构三、删除目的：从跳跃表中删除一个元素x删除操作分为以下三个步骤：（1）在跳跃表中查找到这个元素的位置，如果未找到，则退出*（2）将该元素所在整列从表中删除*（3）将多余的“空链”删除*所谓“记忆化”查找，就是在前一次查找的基础上进行进一步的查找。
它可以利用前一次查找所得到的信息，取其中可以被当前查找所利用的部分。
利用“记忆化”查找可以将一次查找的复杂度变为O(logk)，其中k为此次与前一次两个被查找元素在跳跃表中位置的距离。
下面来看一下记忆化搜索的具体实现方法：假设上一次操作我们查询的元素为i，此次操作我们欲查询的元素为j。
我们用一个update数组来记录在查找i时，指针在每一层所“跳”到的最右边的位置。
如图4.1中橘黄色的元素。
（蓝色为路径上的其它元素）在插入元素j时，分为两种情况：（1）i<=j层开始向上遍历update数组中的元素，直到找到某个元素，它向右指向的元从S素大于等于j，并于此处开始新一轮对j的查找（与一般的查找过程相同）（2）i>j从S层开始向上遍历update数组中的元素，直到找到某个元素小于等于j，并于此处开始新一轮对j的查找（与一般的查找过程相同）图4.2十分详细地说明了在查找了i=37之后，继续查找j=15或53时的两种不同情况。
【复杂度分析】一个数据结构的好坏大部分取决于它自身的空间复杂度以及基于它一系列操作的时间复杂度。
跳跃表之所以被誉为几乎能够代替平衡树，其复杂度方面自然不会落后。
我们来看一下跳跃表的相关复杂度：空间复杂度： O(n) （期望）跳跃表高度： O(logn) （期望）相关操作的时间复杂度：查找： O(logn) （期望）插入： O(logn) （期望）删除： O(logn) （期望）之所以在每一项后面都加一个“期望”，是因为跳跃表的复杂度分析是基于概率论的。
有可能会产生最坏情况，不过这种概率极其微小。
下面我们来一项一项分析。
一、空间复杂度分析O(n)假设一共有n个元素。
根据性质1，每个元素插入到第i层（S）的概率为p i-1 ，则在i第i层插入的期望元素个数为np i-1，跳跃表的元素期望个数为，当p取小于0.5的数时，次数总和小于2n。
所以总的空间复杂度为O(n)二、跳跃表高度分析O(logn)）的概率为p i ，则在第i层插入的期望元素个根据性质1，每个元素插入到第i层（Si数为np i-1。
考虑一个特殊的层：第1+ 层。
层的元素期望个数为 = 1/n2，当n取较大数时，这个式子的值接近0，故跳跃表的高度为O(logn)级别的。
三、查找的时间复杂度分析O(logn)我们采用逆向分析的方法。
假设我们现在在目标节点，想要走到跳跃表最左上方的开始节点。
这条路径的长度，即可理解为查找的时间复杂度。
设当前在第i层第j列那个节点上。
i)如果第j列恰好只有i层（对应插入这个元素时第i次调用随机化模块时所产生的B决策，概率为1-p），则当前这个位置必然是从左方的某个节点向右跳过来的。
ii)如果第j列的层数大于i（对应插入这个元素时第i次调用随机化模块时所产生的A决策，概率为p），则当前这个位置必然是从上方跳下来的。
（不可能从左方来，否则在以前就已经跳到当前节点上方的节点了，不会跳到当前节点左方的节点）设C(k)为向上跳k层的期望步数（包括横向跳跃）有：C(0) = 0C(k) = (1-p)(1+向左跳跃之后的步数)+p(1+向上跳跃之后的步数)= (1-p)(1+C(k)) + p(1+C(k-1))C(k) = 1/p + C(k-1)C(k) = k/p而跳跃表的高度又是logn级别的，故查找的复杂度也为logn级别。
对于记忆化查找（Search with fingers）技术我们可以采用类似的方法分析，很容易得出它的复杂度是O(logk)的（其中k为此次与前一次两个被查找元素在跳跃表中位置的距离）。
四、插入与删除的时间复杂度分析O(logn)插入和删除都由查找和更新两部分构成。
查找的时间复杂度为O(logn)，更新部分的复杂度又与跳跃表的高度成正比，即也为O(logn)。
所以，插入和删除操作的时间复杂度都为O(logn)五、实际测试效果（1）不同的p对算法复杂度的影响表1 进行106次随机操作后的统计结果从表1中可见，当p取1/2和1/e的时候，时间效率比较高（为什么？）。
而如果在实际应用中空间要求很严格的话，那就可以考虑取稍小一些的p，如1/4。
（2）运用“记忆化”查找 (Search with fingers) 的效果分析所谓“记忆化”查找，就是在前一次查找的基础上进行进一步的查找。
它可以利用前一次查找所得到的信息，取其中可以被当前查找所利用的部分。
利用“记忆化”查找可以将一次查找的复杂度变为O(logk)，其中k为此次与前一次两个被查找元素在跳跃表中位置的距离。
表1 进行106次相关操作后的统计结果从表2中可见，当数据相邻被查找元素键值差绝对值较小的时候，我们运用“记忆化”查找的优势是很明显的，不过当数据随机化程度比较高的时候，“记忆化”查找不但不能提高效率，反而会因为跳跃次数过多而成为算法的瓶颈。
合理地利用此项优化，可以在特定的情况下将算法效率提升一个层次。
【跳跃表的应用】高效率的相关操作和较低的编程复杂度使得跳跃表在实际应用中的范围十分广泛。
尤其在那些编程时间特别紧张的情况下，高性价比的跳跃表很可能会成为你的得力助手。
能运用到跳跃表的地方很多，与其去翻陈年老题，不如来个趁热打铁，拿NOI2004第一试的第一题——郁闷的出纳员(Cashier)来“小试牛刀”吧。
例题一：NOI2004 Day1 郁闷的出纳员(Cashier)[点击查看附录中的原题]这道题解法的多样性给了我们一次对比的机会。
用不同的算法和数据结构，在效率上会有怎样的差异呢？首先定义几个变量R –工资的范围N –员工总数我们来看一下每一种适用的算法和数据结构的简要描述和理论复杂度：（1）线段树简要描述：以工资为关键字构造线段树，并完成相关操作。
I命令时间复杂度：O(logR)A命令时间复杂度：O(1)S命令时间复杂度：O(logR)F命令时间复杂度：O(logR)（2）伸展树(Splay tree)简要描述：以工资为关键字构造伸展树，并通过“旋转”完成相关操作。
I命令时间复杂度：O(logN)A命令时间复杂度：O(1)S命令时间复杂度：O(logN)F命令时间复杂度：O(logN)（3）跳跃表(Skip List)简要描述：运用跳跃表数据结构完成相关操作。
I命令时间复杂度：O(logN)A命令时间复杂度：O(1)S命令时间复杂度：O(logN)F命令时间复杂度：O(logN)实际效果评测：（单位：秒）从结果来看，线段树这种经典的数据结构似乎占据着很大的优势。
可有一点万万不能忽略，那就是线段树是基于键值构造的，它受到键值范围的约束。
在本题中R的范围只有105级别，这在内存较宽裕的情况下还是可以接受的。
但是如果问题要求的键值范围较大，或者根本就不是整数时，线段树可就很难适应了。
这时候我们就不得不考虑伸展树、跳跃表这类基于元素构造的数据结构。
而从实际测试结果看，跳跃表的效率并不比伸展树差。
加上编程复杂度上的优势，跳跃表尽显出其简单高效的特点。
