
算法学习(2)--数组、链表和跳表的基本实现与特性
发布日期:2022-02-10 11:37:00
浏览次数:33
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2023年06月02日 19时34分04秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
最新文章
MySQL
2019-12-22 11:35:34
开闭原则「Open Close Principle」
2019-12-22 11:35:34
依赖倒置原则「Dependence Inversion Principle」
2019-12-22 11:35:34
Note-Concurrency
2019-12-22 11:35:32
CentOS7搭建Java开发环境
2019-12-22 11:35:32
微软的cpprestsdk真的不咋地
2019-12-22 11:35:32
antlr4 爬坑日记
2019-12-22 11:35:32
机器学习之训练集,测试集,验证集划分
2019-12-22 11:35:33
python broadcast 和 numpy.sum()函数
2019-12-22 11:35:33
如何在QT环境中使用openCV
2019-12-22 11:35:31
软件自动更新解决方案及QT实现(源码已上传)
2019-12-22 11:35:31
FFmpeg 入门(1):截取视频帧
2019-12-22 11:35:31
C++模板
2019-12-22 11:35:31
线程的切换,线程局部存储
2019-12-22 11:35:31
C++软件开发主要领域及方向
2019-12-22 11:35:31
Note-MySQL
2019-12-22 11:35:31
网站信息的采集系列(三)--百度搜索图片的采集及下载
2019-12-22 11:35:29
网站信息采集系统(四)--京东商品信息的采集
2019-12-22 11:35:30
QT实现的可移动放大缩小的大小嵌套窗体
2019-12-22 11:35:30
QT实现的具有放大功能的小窗口
2019-12-22 11:35:30