链式哈希命中查找运行时间数学证明-创新互联

   《算法导论》中关于链式哈希命中查找运行时间数学证明，一上来就给出公式没看明白，在网上搜了一圈没找到解答心中疑问的文字，于是写下这篇。

创新互联建站坚持“要么做到，要么别承诺”的工作理念，服务领域包括：成都做网站、成都网站制作、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的泊头网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！

   题目是计算在链式哈希表中，在均匀散列的情况下，命中查找的运行时间。

   分析：命中查找的运行时间，就是一个键数目n的函数，按照成本模型便是求命中查找的比较次数随n增长的增长率，即比较次数为n的函数T(n)。

   设要查找键a，a被散列到b链表中。命中查找的比较次数为b链表中排在a前面的元素个数+1.于是题目被转化为键a被插入到b链表后，后续插入的所有键被散列到b链表的个数+1。

设随机变量X表示键a被插入到b链表后，后续插入的所有键被散列到b链表的个数。

设随机变量Yi表示第i次插入键时，键被散列到b链表中的指示器随机变量。（指示器随机变量即当事件发生时为1，不发生时为0.这里表示第i次插入键时，键被散列到b链表中为1，散列到其他链表中为0）

设随机变量Zi表示第i次插入键时，选中a作为插入的键的指示器随机变量。

有

X = ∑<i从1到n>(Zi ∑<k从i+1到n>Yk)        ①

E[Zi] = 1/n                                             ②

E[Yi] = 1/m                                            ③

由上3式得

E[X] = ............ 此处省略20行 ............ = (n-1)/(2m)

题目所求期望即为1 + (n-1)/(2m) = 1 + α/2 - α/(2n)

T(n) = θ(1 + α)

                                                                                               ■

新闻标题：链式哈希命中查找运行时间数学证明-创新互联
本文地址：https://www.cdcxhl.com/article34/cshcpe.html

成都网站建设公司_创新互联，为您提供网站设计公司、静态网站、品牌网站制作、App设计、网站维护、自适应网站

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联