国家集训队2005论文集 魏冉

上传人:mg****85 文档编号:50613452 上传时间:2018-08-09 格式:PPT 页数:15 大小:400KB
返回 下载 相关 举报
国家集训队2005论文集 魏冉_第1页
第1页 / 共15页
国家集训队2005论文集 魏冉_第2页
第2页 / 共15页
国家集训队2005论文集 魏冉_第3页
第3页 / 共15页
国家集训队2005论文集 魏冉_第4页
第4页 / 共15页
国家集训队2005论文集 魏冉_第5页
第5页 / 共15页
点击查看更多>>
资源描述

《国家集训队2005论文集 魏冉》由会员分享,可在线阅读,更多相关《国家集训队2005论文集 魏冉(15页珍藏版)》请在金锄头文库上搜索。

1、让算法的效率“跳起来”! 浅谈“跳跃表”的相关操作及其应用 华东师范大学第二附属中学魏冉“跳跃表” 新生的宠儿 跳跃表(Skip List)是1987年才诞生的一种 崭新的数据结构,它在进行查找、插入、删 除等操作时的时间复杂度均为O(logn),有着 近乎替代平衡树的本领。而且最重要的一点 ,就是它的编程复杂度较同类的AVL树,红 黑树等要低得多,这使得其无论是在理解还 是在推广性上,都有着十分明显的优势。“跳跃表”的结构跳跃表由多条链构成(S0,S1,S2 ,Sh),且满足如下三个条件: 每条链必须包含两个特殊元素:+ 和 - S0包含所有的元素,并且所有链中的元素按照升序排列。 每条链中

2、的元素集合必须包含于序数较小的链的元素集合,即:53 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,按照如下几个步骤进行: 从最上层的链(Sh)的开头开始 假设当前位置为p,它向右指向的节点为q(p与q不

3、一定相邻),且q 的值为y。将y与x作比较 lx=y输出查询成功,输出相关信息 lxy从p向右移动到q的位置 lxy从p向下移动一格 如果当前位置在最底层的链中(S0),且还要往下移动的话,则输出 查询失败53 53 53 45 45 37 30 30 30 29 15 11 11 11 11 - - - - + + + + 查询元素53的全过程S0 S1 S2 S3 查找成功!基本操作二 插入目的:在跳跃表中插入一个元素 x 插入操作由两部分组成: 查找插入的位置和插入对应元素。为了确定插入的“列高”,我们引入一个随机决策模块: 产生一个0到1的随机数rr random() 如果r小于一个概

4、率因子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高度+1 结束53 - -

5、- - S0 S1 S2 S3 基本操作三 删除目的:从跳跃表中删除一个元素 x 删除操作分为以下三个步骤: 在跳跃表中查找到这个元素的位置,如果未找到,则退出 将该元素所在整列从表中删除 将多余的“空链”删除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,它决定了跳跃表的高度, 并影响到了整个数据结构的效率。 让我们来看看在实际评测过程中,不同的P在时空效率上的

6、差异。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.82136.007跳

7、跃表的应用 高效率的相关操作和较低的编程复杂度使得跳跃表在实际 应用中的范围十分广泛。尤其在那些编程时间特别紧张的 情况下,高性价比的跳跃表很可能会成为你的得力助手。您正为找不到合适的数据结构而感到烦恼吗?您正为自己编写程序的效率高低而感到担忧吗?您正为陷入R-B tree的深渊又无法自拔而感到苦闷吗?朋友!试试跳跃表吧!它将给您的编程带来超高的效率与无尽的快乐!机不可失,时不再来!详情请致电:1381xxxxxxx跳跃表的应用 NOI2004 Day1 郁闷的出纳员(Cashier) 抽象题意:要求维护这样一个数据结构,使得它支持以下四种操作: I(x)插入一个值为 x 元素 A(x)现有全

8、体元素加上一个值 x S(x)现有全体元素减去一个值 x F(i)查找现有元素中第 i 大的元素值 (x为105级别) 同时还要保持这样一个性质: 现有的元素必须都大于一个特定的值min,小于min的要删去。我们利用一个虚拟的“零线”来表示0在数据结构中的相对位置。这样在 进行A和S操作的时候,只要对“零线”进行调整即可,并不需要对所有元 素的值做全面的修改。而在做S操作时,为了维持题意中的性质,要注意将 值低于(“零线”+min)的元素删除。支持这些操作的数据结构有很多,比如说线段树,伸展树,跳跃表等。跳跃表的应用 NOI2004 Day1 郁闷的出纳员(Cashier)评测结果:(单位:秒

9、)Test1Test2Test3Test4Test5Test6Test7Test8Test9Test10 线段树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)

10、 O(logN) O(logN) 跳跃表 O(logN) O(1) O(logN) O(logN) 1. 空间复杂度O(n)2. 摆脱实数的约束3. 极小的编程复杂度能够使你很短的内解决此题!跳跃表的应用 HNOI2004 Day1 宠物收养所 (Pet) 抽象题意:维护一个数据结构,使得它支持以下两种操作: 插入一个元素 x (0x231) 给定一个元素y,删除现有与y差值最小的元素x (|x-y|为最小) 所有操作次数不超过80000 思考.线段树?如果采取边做边开空间的策略,勉强可以缓解内存的压 力。但此题对内存的要求很苛刻,元素相对范围来说也比 较少,如果插入的元素稍微分散一些,就很有可能使得空 间复杂度接近O(nlogR)!何况如果拓展一下,插入的元素不是整数而是实数呢?跳跃表!好!总结 跳跃表作为一种新兴的数据结构,以相当高 的效率和较低的复杂度散发着其独特的光芒 。和同样以编程复杂度低而闻名的“伸展树 ”相比,跳跃表的效率不但不会比它差,甚 至优于前者。“跳跃表”这个名字有着其深远的意义!谢谢大家Thank you

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 生活休闲 > 科普知识

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号