算法学习(2)--数组、链表和跳表的基本实现与特性
发布日期:2022-02-10 11:37:00
浏览次数:50
分类:技术文章
本文共 543 字,大约阅读时间需要 1 分钟。
一、数组
- 数组是一段连续地址的内存,使用内存管理器(memory controller)访问,访问的时间复杂度为O(1)。
- 增(删)元素:插入(删除)一个元素,该位置后元素全部后移(前移),时间复杂度为O(n)。
- 数组扩张时,如果原有内存大小不能满足需求,则开辟一块原来大小两倍的内存,用以复制旧数组。
二、链表
- node,有单链表、双向链表、循环链表,pHead/pTail/构造函数。
- 增删不涉及群移操作,移动和修改操作的时间复杂度为O(1)。
- 访问元素节点的时间复杂度为线性复杂度O(n)。
- LRU cache利用链表。
三、跳表
- Skip List,只能用于元素有序的情况。
- 跳表对标的是平衡树AVL和二分查找,是一种插入/删除/搜索都是O(logn)的数据结构。
- 优势是原理简单、容易实现、方便拓展、效率高,在一些热门的项目中来替代平衡树,如Redis,LevelDB(Google,Jeff Dean)
- 跳表是一维数组升维实现的,在思考提升链表插座的效率的过程中,原链表如下:
建立第一级索引:
建立第二级索引:
建立多级索引:
5. 现实中跳表的形态
6.跳表查找的时间复杂度为O(logn);增加和删除需要维护更新索引,时间复杂度为O(logn),空间复杂度为O(n)。
转载地址:https://blog.csdn.net/Fan_z_0802/article/details/107828761 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.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
mysql表名长度_JavaWeb之MySQL(一)
2019-04-21
mysql服务器语法_Mysql语法
2019-04-21
python双击py一闪_Python脚本在双击.py时无法正常运行
2019-04-21
redis logfile为空_关于Redis(二)
2019-04-21
git更换_git命令
2019-04-21
hp-ux 查看系统负载_Linux性能调优 | 平均负载的理解和分析
2019-04-21
elementui的tree组件页面显示不出数据_vue路由及组件
2019-04-21
python 动态tabel的数据爬取_使用requests爬取python岗位招聘数据
2019-04-21
input js number 整数_JS基础简单小结(1)
2019-04-21
二阶差分预测后数据还原公式_xgboost系列丨xgboost原理及公式推导
2019-04-21