从摔鸡蛋问题讲跳表的原理

关于摔鸡蛋问题（曾经是谷歌的一道面试题），我相信大家都有所了解。知乎上有很多高手在讨论这个问题，我这里说一下个人的理解。

摔鸡蛋问题

给你K个鸡蛋，让你测试鸡蛋壳的硬度，测量的方法就是从不同高度的楼层向下扔，如果鸡蛋在第i层摔碎了而在第i-1层没摔碎，那么我们就知道鸡蛋壳的硬度了，即用层数代表鸡蛋壳的硬度。并且假设鸡蛋肯定能用某一层的层数来表示。现在的问题是，用K个鸡蛋，最坏情况下最少需要多少次才能测试出鸡蛋壳的硬度？

例如只有一个鸡蛋，那么为了保证在测出鸡蛋壳硬度之前鸡蛋不破裂，只能一层一层的试。如果楼的高度有N层，那么最查情况需要N次实验。

如果有两个鸡蛋呢？假设最坏情况最少需要m次实验，那么第一只鸡蛋只能最多在第m层进行实验，如果第m层没有摔碎，那么接下来就必须在第m+m-1层进行实验,如果第m层摔碎了，那么第二只鸡蛋就必须从第1层到第m-1层逐层进行实验，这样能保证最坏情况下至多实验m次。依次类推，那么我们求得一个实验的楼层间隔序列m, m-1, m-2,…… 1，这样能保证m最小，那么也就是说m取1+2+……+m>=N的最小值。

对于任意数量的鸡蛋和任意高度的楼层并没有一个直接的公式能够计算出最坏情况最少需要多少次实验，实际上这是一个动态规划问题。

那么，什么是跳表？这和跳表有什么关系呢？

跳表

假如我们要存储N个字符串，字符串的长度不一，我们如何能够高效率的存储这些字符串呢？如果我们给每个字符串分配同样大小的内存，那么每个字符串开销和最长的字符串开销一样，这样必然会极度浪费空间。但是这样存储的好处是可以很快的进行字符串查找，例如可以用二分查找。

现在我们要做到，既要存储上不浪费空间，而且查找效率也要能够很好，怎么办？字典树，平衡二叉树？这些都可以，但是要存储这种树结构又不免的浪费一些空间，而且实现上比较复杂。这里面就要用到跳表了。

要使得存储高效，那么最简单的办法就是字符串有多长，就给其分配那么大的空间，不需要大小固定一致，并且每个字符串前用固定几个字节存储其长度，这样就可以很方便的从存储的开始处识别出每个字符串。那么问题来了，这样做不能得到很好的查找效率，因为二分的方法在这里面无用武之地。跳表的思想就是，在这个字符串序列之间插入一定数量的指针，使得查找时不是仅仅查找后面相邻的字符串，而是跳过一定数量的字符串。

如图在第一个表中查找f需要6次查找，而在第二个表中只需5次。那么现在的问题是，如果字符串的数目是N个，我们需要多少个跳跃指针？每个指针之间的间隔又是多少呢？

假设这里如果你不在乎额外的存储指针的空间开销，那么可以用N个指针，每个指针指向一个字符串，而且这样可以利用二分查找，在很多规模不算太大的问题当中，这种方法相当的好。

但是如果你觉得存储指针都很浪费空间，那么就需要跳表了。这个和摔鸡蛋问题是一样的，没有一个公式能够告诉你应该怎么做才是最优的。实际上最常用的策略就是等间隔插入指针，并且效果不错。

假设表长度为N，需要等间隔插入K个指针，那么最差情况下需要K+N/K次查找来查找一个元素，即y=K+N/K，对K求导，y'=1-N/K2，让y'=0求得y取最小值时k的值，1-N/K2=0 => K2 = N => K=sqrt(N)，即最优情况下需要sqrt(N)个指针，每个指针的间隔也是sqrt(N)。

例如表长度为100万，那么K=1000时，最坏需要1000+1000=2000次查找来查找一个元素，而顺次查找期望是50万次查找一个字符串。虽然有很多方法可以解决这种既要求存储效率高又要求查找速度也要很好的问题，但是无疑跳表的思想是最简单的，并且很多实际的问题就是用这种方法解决的。总之一句话，简单就是美。

参考资料

• https://www.zhihu.com/question/19690210

： » 从摔鸡蛋问题讲跳表的原理