版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、让算法的效率“跳起来”! 浅谈“跳跃表”的相关操作及其应用 华东师范大学第二附属中学 魏冉“跳跃表” 新生的宠儿 跳跃表(Skip List)是1987年才诞生的一种崭新的数据结构,它在进行查找、插入、删除等操作时的时间复杂度均为O(logn),有着近乎替代平衡树的本领。而且最重要的一点,就是它的编程复杂度较同类的AVL树,红黑树等要低得多,这使得其无论是在理解还是在推广性上,都有着十分明显的优势。“跳跃表”的结构跳跃表由多条链构成(S0,S1,S2 ,Sh),且满足如下三个条件:1.每条链必须包含两个特殊元素:+ 和 -2.S0包含所有的元素,并且所有链中的元素按照升序排列。3.每条链中的元
2、素集合必须包含于序数较小的链的元素集合,即:hSSSS.210hSSSS.210hSSSS.21053 53 53 45 45 37 30 30 30 29 15 11 11 11 11 - - - - + + + + S0 S1 S2 S3 跳跃表的实例“跳跃表” 的时空效率 空间复杂度: O(n) (期望) 跳跃表高度: O(logn)(期望)相关操作的时间复杂度:查找: O(logn)(期望)插入: O(logn)(期望)删除: O(logn)(期望)基本操作一 查找目的:在跳跃表中查找一个元素 x在跳跃表中查找一个元素x,按照如下几个步骤进行:I.从最上层的链(Sh)的开头开始II.假
3、设当前位置为p,它向右指向的节点为q(p与q不一定相邻),且q的值为y。将y与x作比较lx=y输出查询成功,输出相关信息lxy从p向右移动到q的位置lxy从p向下移动一格III.如果当前位置在最底层的链中(S0),且还要往下移动的话,则输出查询失败53 53 53 45 45 37 30 30 30 29 15 11 11 11 11 - - - - + + + + 查询元素53的全过程S0 S1 S2 S3 查找成功!基本操作二 插入目的:在跳跃表中插入一个元素 x 插入操作由两部分组成:查找插入的位置和插入对应元素。为了确定插入的“列高”,我们引入一个随机决策模块:产生一个0到1的随机数r
4、r random()如果r小于一个概率因子P,则执行方案A,if rpthen do A否则,执行方案Belse do B列的初始高度为1。插入元素时,不停地执行随机决策模块。如果要求执行的是A操作,则将列的高度加1,并且继续反复执行随机决策模块。直到第i次,模块要求执行的是B操作,我们结束决策,并向跳跃表中插入一个高度为i的列。基本操作二 插入 假设我们现在要插入一个元素40到已有的跳跃表中。37 30 30 30 29 15 - - - - S0 S1 S2 S3 插入的位置53 53 53 45 45 + + + + 40 40 4040 高度+1随机化模块运行状况:高度=4高度+1高度
5、+1 结束53 - - - - S0 S1 S2 S3 基本操作三 删除目的:从跳跃表中删除一个元素 x删除操作分为以下三个步骤:1.在跳跃表中查找到这个元素的位置,如果未找到,则退出2.将该元素所在整列从表中删除3.将多余的“空链”删除11 11 11 11 53 53 53 45 45 37 30 30 30 29 15 + + + + 53 53 53 45 45 37 30 30 30 29 15 - - - + + + S0 S1 S2 概率因子 P 对跳跃表的影响在插入操作中,我们引入了一个概率因子P,它决定了跳跃表的高度,并影响到了整个数据结构的效率。让我们来看看在实际评测过程中
6、,不同的P在时空效率上的差异。P 平均操作时间 平均列高 总结点数 每次查找跳跃次数(平均值) 每次插入跳跃次数(平均值) 每次删除跳跃次数(平均值) 2/3 0.0024690 ms 3.004 91233 39.87841.60441.5661/2 0.0020180 ms1.995 60683 27.80729.94729.0721/e 0.0019870 ms1.584 47570 27.33228.23828.4521/4 0.0021720 ms1.33040478 28.72629.47229.6641/8 0.0026880 ms1.14434420 35.14735.8213
7、6.007跳跃表的应用 高效率的相关操作和较低的编程复杂度使得跳跃表在实际应用中的范围十分广泛。尤其在那些编程时间特别紧张的情况下,高性价比的跳跃表很可能会成为你的得力助手。您正为找不到合适的数据结构而感到烦恼吗?您正为自己编写程序的效率高低而感到担忧吗?您正为陷入R-B tree的深渊又无法自拔而感到苦闷吗?朋友!试试跳跃表吧!它将给您的编程带来超高的效率与无尽的快乐!机不可失,时不再来!详情请致电:1381xxxxxxx跳跃表的应用 NOI2004 Day1 郁闷的出纳员(Cashier) 抽象题意:要求维护这样一个数据结构,使得它支持以下四种操作:I(x)插入一个值为 x 元素A(x)现
8、有全体元素加上一个值 xS(x)现有全体元素减去一个值 xF(i)查找现有元素中第 i 大的元素值(x为105级别)同时还要保持这样一个性质:现有的元素必须都大于一个特定的值min,小于min的要删去。 我们利用一个虚拟的“零线”来表示0在数据结构中的相对位置。这样在进行A和S操作的时候,只要对“零线”进行调整即可,并不需要对所有元素的值做全面的修改。而在做S操作时,为了维持题意中的性质,要注意将值低于(“零线”+min)的元素删除。 支持这些操作的数据结构有很多,比如说线段树,伸展树,跳跃表等。跳跃表的应用 NOI2004 Day1 郁闷的出纳员(Cashier)评测结果:(单位:秒)Tes
9、t1Test2Test3Test4Test5Test6Test7Test8Test9Test10线段树0.0000.0000.0000.0310.0620.0940.1090.2030.2650.250伸展树0.0000.0000.0160.0620.0470.1250.1410.3600.4530.422跳跃表0.0000.0000.0000.0470.0620.1090.1560.3680.4380.375I命令时间复杂度 A命令时间复杂度 S命令时间复杂度 F命令时间复杂度 线段树O(logR) O(1) O(logR) O(logR) 伸展树 O(logN) O(1) O(logN) O(logN) 跳跃表 O(logN) O(1) O(logN) O(logN) 1. 空间复杂度O(n)2. 摆脱实数的约束3. 极小的编程复杂度能够使你很短的内解决此题!跳跃表的应用 HNOI2004 Day1 宠物收养所 (Pet) 抽象题意:维护一个数据结构,使得它支持以下两种操作: 插入一个元素 x (0 x231) 给定一个元素y,删除现有与y差值最小的元素x (|x-y|为最小)所有操作次数不超过80000思考.线段树? 如果采取边做边开空间的策略,勉强可以缓解内存的压力。但此题对内存的要求很苛刻,元素相对范围来说也比较少,如果插入的元素稍微分散一些,就很有可能使得空间复杂度
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 激发探索欲望的阅读清单
- 比例尺与数学学习方法指导
- 人教版高中生物教材目录精讲
- 地理八年级人教版地理位置描述
- 苏教版八年级下册语文学习进度
- 高中化学人教版新旧目录对比
- 全面解析人教版高一英语单元重点
- 新版小明的一天北师大版教案解析
- 探索人教版名著的精髓与魅力
- 漫画人教版历史创新教学引领潮流
- 八年级语文上册 第一单元 单元测试卷(人教广东版 2024年秋)
- 2024年湖南省中考道德与法治试题卷(含答案)
- 汽车汽车制造行业数据分析与管理
- 安徽省2024年中考道德与法治真题试卷【附真题答案】
- 五年级科学上册(大象版)第3课材料与保温(教学设计)
- 2024年喀什地区行署机关事业单位公开遴选【重点基础提升】模拟试题(共500题)附带答案详解
- 2024年江西省中考生物试卷附答案
- 重大事故隐患重点事项排查清单1
- 2024年机关事业单位工人招聘《机动车驾驶员》技师 考试题库与答案
- 国家职业技能鉴定考评员培训讲义
- 小学音乐教师晋级述职报告
评论
0/150
提交评论