电子商务网站设计,手机端做网站软件,铜陵app网站做招聘,网站管理助手4.0教程跳跃表的基本内容#xff1a;
对于一个有序序列#xff0c;链表相对于数组来说#xff0c;删除和插入的效率要快很多#xff0c;只需要改变指针的指向#xff0c;但是在查找的时候#xff0c;数组就要更占优势一些#xff0c;可以随机访问#xff0c;然而链表需要从头…跳跃表的基本内容
对于一个有序序列链表相对于数组来说删除和插入的效率要快很多只需要改变指针的指向但是在查找的时候数组就要更占优势一些可以随机访问然而链表需要从头开始遍历最坏的情况下可能达到了O(n),为了改变链表的这一弊端人们就想出了利用空间换时间的策略尝试给链表加个索引假设我们当前有如下所示的普通链表
我们要查找18需要比较8次 但如果如下所示我们给当前链表添加一层索引那么只需要比较5次 如果我们给当前链表添加两层索引(如下所示)那么只需要比较4次 跳表的第一层存储的是所有的元素每个节点存在两个指针指向后继节点和下一层的节点查找的时候从最高层开始逐层比较直到第一层 对于跳跃表来说假设我们现在想要插入数据我们不但要在链表中插入数据还要去更新索引如果直接插入数据而不更新索引那么很有可能出现两个索引之间存在大量的数据同时也失去了创建索引的意义那么要如何更新索引呢
上层节点个数应该是下层节点个数的二分之一因此我们希望这个新节点添加到上一层的概率是二分之一最简单的方式就是抛硬币因为正反面的概率都是二分之一所以我们只要让它在0和1之间随机如果是0就停止如果是1就继续最后出现的次数k,就代表我们需要在第一层到第k层之间添加索引当然我们也不能让它无限增长所以我们还需要添加一个最大值的限制
public int getRandom(){int k1;Random randomnew Random();//random.nextBoolean()返回一个随机的 boolean 值,即 true 或 falsewhile(random.nextBoolean()kMAX_VALUE){k;}return k;
}跳跃表的增删改查
比如我们添加一个节点为13随机值为2 那么我们只需要在第一层和第二层加入13即可 删除操作就比较简单了直接将我们节点和跨越的层数删除即可 时间复杂度 第一层的索引节点数为n个第二层为n/2个那么第K层的索引节点数为
注意当某层的索引节点只有两个时我们就不增加索引了 下述中的2为当索引个数为2时我们就不再添加索引了h为跳跃表的高度 如果我们每一层要遍历X个节点那么在跳表中查找的时间复杂度就为O(Xlogn),可认为O(logn)
由于插入和删除的时间复杂度都是O(1),时间主要花费在查找元素的位置所以插入和删除的时间复杂度都为O(logn)
