跳跃表的证明与实现

想写一个简单的东西来维护序列？

不想写红黑树来维护？

想口胡算法？

尝试==跳跃表==吧！

#1 跳跃表是个什么东东？

跳跃表其实起源于链表的优化。

首先，我们看看链表的格式：

\[ {1 \xrightarrow{}{} 2 \xrightarrow{}{} 4\xrightarrow{}{} 5} \]

此时，我们让序列是有序的，以方便查找。

注意，此时我们已经有一个插入\[\Theta(n/2)\]的算法了。

提高效率？

\[ \color{red}{1} \color{black}{\xrightarrow{}{} 2 \xrightarrow{}{} 4} \xrightarrow{}{} \color{red}{5} \color{black}{ \xrightarrow{}{} 6 \xrightarrow{}{} 7}\]

每一次先搜标红的点，找到刚好大于等与红标记但小于下一个红标记的点。

复杂度: \[\Theta(\text{红标记个数/2}+\text{总数/红标记个数/2})\]

当红标记个数等于总数开根时，\[ \Theta(\sqrt{n}) /2\]

然后，似乎红标记也可以进行同样的操作，复杂度可以在开个根。

然后继续对上一层标记操作，又可以开根…………

但是，到了最后，向下跳的层数会大于等于向右移的次数，我们就令最大的层数为k。

列出方程，即求
\[ \min{(k + k (\log_{k}{n})/2)} \]
解得
\[ k = \ln n \]
即
\[ e^k = n \]
此时复杂度为
\[ \Theta({\ln n}) \]
其实这里似乎咕了

#2 实现？

跳跃表的证明与实现

原文：https://www.cnblogs.com/dgklr/p/11166269.html