跳表尺寸符号约定:
符号约定
文章图片
- 元素节点个数N， 层高h，
- 最高层为第h层，节点列表的上一层为第1层
因此 层i节点个数为: $N 2^{-i}$跳表时间复杂度算式
跳表每一层所需步骤
每一层都是有序的，在有序的第i层上进行二分查找 所需要的步骤： $$$$ #### 跳表各层所需总步骤 > 总步骤 为 各层所需步骤之和： $$ \sum_i^h(层i所需步骤 )=\sum_i^h(log(N 2^{-i}) ) = \sum_i^h(logN - i ) =h log(N)- \sum_i^h( i )=h log(N)-\frac{h}{2}(h+1) $$
层i所需步骤=log(层i节点个数)=log(N 2^{-i}) = logN - i
小结
即 跳表时间步骤为： $h log(N)-\frac{h}{2}(h+1)$ ，其中：N为节点个数，h为层高
【skiplist跳表 时间复杂度算式】$\frac{h}{2}(h+1)$ 是与输入规模N无关的， 且层高h通常不大，可见 跳表时间复杂度为 O(h logN)
