专栏首页算法半岛数据结构与算法-跳表

数据结构与算法-跳表

在学习二分查找时,我们知道二分查找需要依赖数组的随机访问的特性进行查找,而链表不具有随访问的特性,因此不能使用传统上的二分查找方法了。为了使得链表支持类似二分查找的算法,对原始的链表进行修改,修改后的链表就是跳跃表,简称跳表。跳表支持快速的插入、删除、查找操作,是一种动态的数据结构。

跳表的理解

我们知道对于链表中存储的数据有序的单链表,我们需要查找链表中的某个数据,需要从头到尾遍历,查找的时间复杂度位 O(n),如下所示:

我们对原始链表加一级索引,如下所示:

如下图所示,对于查找值为6的节点,在原始节点上查找需要6次,而通过第一级索引进行查找,如下图所示,只需要5次,减少了查找次数。

我们再到第一级索引上在再加索引,如下图所示:

对于查找值为6的节点如下所示,查找次数为6次。

由于这个数据量不大,查找效率提升的不明显,对于数据量较大的时候,查找效率提高很快。

时间复杂度分析

首先来分析对于有 n个节点的链表,需要建立多少级索引。根据上面的例子可以得到,如果我们每两个节点会提取一个节点作为一个索引节点,那么第一级索引节点的个数为 n/2,第二级索引节点的个数为 n/4,依此类推,则第K级的索引节点的个数为 n/(2^k)

假设索引有 h级,且第 h级的索引节点个数为2,如下图所示。则我们可以得出 n/(2^h)=2,这样可以得到 h=logn-1这里的 log是指以2为底),加上链表本身的一层,则整个跳表的高度为 logn。我们在跳表中查询某个数据时,如果每一层都需要遍历 m个节点,那么在跳表中查询某个数的时间复杂度为 O(m*logn)

跳表空间复杂度分析

跳表查找效率的提高是通过建立多级索引实现的,而建立索引肯定需要消耗内存空间。对于跳表的内存空间分析并不难,对于有 n个节点的链表,第一级索引节点的个数为 n/2,第二级索引节点的个数为 n/4,最后一级的索引节点的个数为2,我们可以得出一个等比数列: n/2+n/4+n/8+...+4+2=n-2,因此跳表的空间复杂度为 O(n)

本文分享自微信公众号 - 算法半岛(jacob2359),作者:算法半岛

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《批判性思维工具(Critical Thinking)》-读书笔记(一)

    在本书的前言中描述道:思维方式决定着行为方式。思维决定行为,感受和需求。这就是说不同的思维方式会导致不同的行为、感受和需求,这一点我相信大多数人都会产生...

    用户3470542
  • 数据结构与算法-树

    用户3470542
  • 数据结构与算法-二叉树(二)

    二叉查找树是一种特殊的二叉树,它支持动态的数据集合的快速插入、删除和查找操作。二叉查找树的一般结构如下图所示:

    用户3470542
  • 深入理解MySQL索引底层数据结构与算法

    在开始讲这一小节之前,我们先来看一下在数据库没有加索引的情况下,SQL中的where字句是如何查找目标记录的。

    用户6182664
  • MySQL 索引(3)

    索引是对数据库表中一列或多列的值进行排序的一种结构,使用索引可快速访问数据库表中的特定信息。

    兜兜毛毛
  • 一篇文章讲透MySQL为什么要用B+树实现索引

    索引这个词,相信大多数人已经相当熟悉了,很多人都知道MySQL的索引主要以B+树为主,但是要问到为什么用B+树,恐怕很少有人能把前因后果讲述的很完整。本文就来从...

    用户1260737
  • 不准犹豫!再有人问你为什么MySQL用B+树做索引,就把这篇文章发给她

    索引这个词,相信大多数人已经相当熟悉了,很多人都知道MySQL的索引主要以B+树为主,但是要问到为什么用B+树,恐怕很少有人能把前因后果讲述的很完整。本文就来从...

    帅地
  • B树?这篇文章彻底看懂了!

    索引,相信大多数人已经相当熟悉了,很多人都知道 MySQL 的索引主要以 B+ 树为主,但是要问到为什么用 B+ 树,恐怕很少有人能把前因后果讲述完整。本文就来...

    程序员追风
  • 再有人问你为什么MySQL用B+树做索引,就把这篇文章发给她

    索引这个词,相信大多数人已经相当熟悉了,很多人都知道MySQL的索引主要以B+树为主,但是要问到为什么用B+树,恐怕很少有人能把前因后果讲述的很完整。本文就来从...

    Java3y
  • Kubernetes 集群规模杂谈

    早在 Kubernetes 1.2 时候,就已经宣布达到 1000 节点的规模了,在 1.6 版本更达到了 5000 节点的规模。各大厂也都有了各自的超大规模单...

    崔秀龙

扫码关注云+社区

领取腾讯云代金券