从redis跳表实现理解查找时间复杂度

list123342

​之前一直不太懂,为什么跳表的平均时间复杂度为O(logN)
但是后来看了下http://blog.xiaoheshang.info/?p=248 算是理解了一些,再结合自己的思考,记录一下
首先,需要理解刚才那篇文章中的 "如果每2^i个节点都指向前面2^i个节点，寻找一个节点的复杂度变成logn（类似于二分查找）", 这个应该没什么问题
那么问题来了,为什么随机的层数也能保证logN的复杂度?
原因就在于,这里说的随机,并不是完全的随机一个层数出来,而是通过随机的算法,算出一个并不随机的层数来
以redis中的随机层数的算法来看

int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

这里假设 ZSKIPLIST_P 为2 (实际为4,便于理解设置为2),这段代码我们可以理解为,落到层数为i + 1的概率为0.5^i
而反过来理解,每两个节点出现层数为2的期望就是1,每4个节点出现第三层的期望也为1,每8个节点出现第四层(0.5^3)的期望为1 (期望值 = 单个概率 * 数量)
正是基于此,如果我们的数据量越大,越是可以接近期望的值,所以,我们可以认为,我们实现了 "如果每2^i个节点都指向前面2^i个节点"的效果,也就是说,查找的平均复杂度为O(logN)