数组、链表、跳表 - 图1

跳表

如何给有序的链表加速

原始链表：
image.png
添加第一级索引
image.png
进一步提高查找速度，添加第二级索引
image.png
以此类推
image.png

跳表查询的时间复杂度分析

每一级索引的个数：n/2、n/4、n/8、....n/(k^2)
假设有 h 级索引，最高级的索引有2个节点，那么 n/(h^2) = 2 ,则 h=log2(n)-1
所以跳表查询的时间复杂度为 O(logn)
注意 跳表在增加和删除元素的时候，所有的索引都要更新一遍，所以时间复杂度也为 O(logn)

跳表的空间复杂度分析

image.png

关于做算法题

如果看到题目的时候很懵，没有一点思路怎么办？

  1. 先思考暴力是否可以
  2. 分析基本情况
  3. 泛化，找最近 重复 子问题