• 欢迎访问web前端中文站,JavaScript,CSS3,HTML5,web前端demo
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏web前端中文站吧

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

JAVA web前端中文站 2年前 (2017-12-23) 706次浏览 已收录 0个评论

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

更多精彩内容请看 web 前端中文站
http://www.lisa33xiaoq.net 可按 Ctrl + D 进行收藏

摔鸡蛋问题

给你 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 万次查找一个字符串。虽然有很多方法可以解决这种既要求存储效率高又要求查找速度也要很好的问题,但是无疑跳表的思想是最简单的,并且很多实际的问题就是用这种方法解决的。总之一句话,简单就是美。

在学习了跳表的原理之后,对 java 的跳表原理应该有了更深的理解,接下来可以学习JAVA 实现跳表(SKIPLIST)

参考资料

【注:本文源自网络文章资源,由站长整理发布】


web 前端中文站 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:从摔鸡蛋问题讲跳表的原理
喜欢 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址