算法学习(2)--数组、链表和跳表的基本实现与特性
发布日期:2022-02-10 11:37:00 浏览次数:50 分类:技术文章

本文共 543 字,大约阅读时间需要 1 分钟。

一、数组

  1. 数组是一段连续地址的内存,使用内存管理器(memory controller)访问,访问的时间复杂度为O(1)。
  2. 增(删)元素:插入(删除)一个元素,该位置后元素全部后移(前移),时间复杂度为O(n)。
  3. 数组扩张时,如果原有内存大小不能满足需求,则开辟一块原来大小两倍的内存,用以复制旧数组。

 

二、链表

  1. node,有单链表、双向链表、循环链表,pHead/pTail/构造函数。
  2. 增删不涉及群移操作,移动和修改操作的时间复杂度为O(1)。
  3. 访问元素节点的时间复杂度为线性复杂度O(n)。
  4. LRU cache利用链表。

 

三、跳表

  1. Skip List,只能用于元素有序的情况。
  2. 跳表对标的是平衡树AVL和二分查找,是一种插入/删除/搜索都是O(logn)的数据结构。
  3. 优势是原理简单、容易实现、方便拓展、效率高,在一些热门的项目中来替代平衡树,如Redis,LevelDB(Google,Jeff Dean)
  4. 跳表是一维数组升维实现的,在思考提升链表插座的效率的过程中,原链表如下:

建立第一级索引:

建立第二级索引:

建立多级索引:

5. 现实中跳表的形态

6.跳表查找的时间复杂度为O(logn);增加和删除需要维护更新索引,时间复杂度为O(logn),空间复杂度为O(n)。

转载地址:https://blog.csdn.net/Fan_z_0802/article/details/107828761 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:利用道格拉斯·普客法(DP法)压缩矢量多边形(C++)
下一篇:(五)建筑物多边形化简系列——最小外接矩形的获取

发表评论

最新留言

做的很好,不错不错
[***.243.131.199]2024年03月25日 10时35分55秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

深度linux内核升级,深度操作系统 2020.11.11 更新发布:内核升级 2019-04-21
sql 拆解函数_SQL入门50题详解(含知识点讲解及代码运行步骤拆解) 2019-04-21
java和python交互 jni_Python基于pyjnius库实现访问java类 2019-04-21
macbook pro 卸载mysql_MacBook Pro全新重装OS X Yosemite 2019-04-21
已达到计算机的连接数最大值无法再同此远程计算机连接_电脑远程访问已达到计算机的连接数最大值怎么办?解决方法很简单... 2019-04-21
mysql表名长度_JavaWeb之MySQL(一) 2019-04-21
mysql服务器语法_Mysql语法 2019-04-21
pdf 模版 汉字和数字_《吉林大学珠海学院毕业论文(设计)模板》(汉字标题版) .pdf... 2019-04-21
python bottle部署_nginx+uwsgi+bottle python服务器部署 2019-04-21
python双击py一闪_Python脚本在双击.py时无法正常运行 2019-04-21
redis logfile为空_关于Redis(二) 2019-04-21
mysql 设计两个主键都不可重复_程序员面试备战篇:18个经典MySQL面试专题解析(干货分享答案)... 2019-04-21
下列关于python2.x和3.x的区别说法正确_Python 2.x和Python 3.x版本有哪些区别?【面试题详解】... 2019-04-21
git更换_git命令 2019-04-21
hp-ux 查看系统负载_Linux性能调优 | 平均负载的理解和分析 2019-04-21
elementui的tree组件页面显示不出数据_vue路由及组件 2019-04-21
android hook sensor数据_最近,又有人在谈论Android的前景了!深入解析趋势及必备技术点... 2019-04-21
python 动态tabel的数据爬取_使用requests爬取python岗位招聘数据 2019-04-21
input js number 整数_JS基础简单小结(1) 2019-04-21
二阶差分预测后数据还原公式_xgboost系列丨xgboost原理及公式推导 2019-04-21