1.数组的时间复杂度：append -----O(1) lookup -----O(1) insert -----O(n) delete-----O(n)
2.链表的时间复杂度：append -----O(1) lookup -----O(n) insert -----O(1) delete -----O(1)
选择哪种数据结构与业务系统有关，但是是否有一种数据结构能综合这两种的优点？引出今天的重点：跳表，也就是redis的zset的数据结构
3.skip list
特点：只能用于元素有序的情况，所以对标的是平衡树以及二分查找树，插入/删除/查找得失时间复杂度都是O(log n)
对于一维的数据进行加速，一般来说就是升为二维，也就是昨天说到的，利用空间换取时间，一级索引是N/2, 二级索引是N/4,空间复杂度为O(n), 如图
leet code刷题方法：
1. 5-10分钟思考
2. 有思路的话自己做题，一点思路没有赶紧写看题解
3.已有的题解背诵。默写直到熟料
4.复制题目，去掉cn，上国际站
5.高级算法模版
一道题刷五遍
1.数组的时间复杂度：append -----O(1) lookup -----O(1) insert -...
数组 链表 跳表 
Array（数组） Array 增加、删除元素，需要挪动平均一半数组长度的元素，所以，对于 Array 来说，增删...
初识跳表 为什么需要跳表？ 首先，跳表是链表的一种优化模型。 对于有序的数组来说，我们查询的时间复杂度可以通过二分...
283. 移动零 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 ...
基础数据结构 数组、链表、跳表的原理和实现 类型链接数组https://blog.csdn.net/qq_3025...
跳表是什么 跳表的实现基于链表，弥补了链表不便于查找的缺点，所以跳表其实不是表(table)而是链(list)。跳...
跳表的定义 跳表(SkipList)：增加了向前指针的链表叫做跳表。跳表全称叫做跳跃表，简称跳表。跳表是一个随机化...
跳表的定义 跳表(SkipList)：增加了向前指针的链表叫做跳表。跳表全称叫做跳跃表，简称跳表。跳表是一个随机化...
数组 链表 跳表 基础 数组：一段连续的内存空间，增删时间复杂度O(n),查找 O(1)，每次增删会移动index...
本文标题：2020-05-01 数组，链表以及跳表
本文链接：https://www.haomeiwen.com/subject/tyvcghtx.html
网友评论