资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

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

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

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

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

   分析:命中查找的运行时间,就是一个键数目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 = ∑(Zi ∑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 + α)

                                                                                               ■


名称栏目:链式哈希命中查找运行时间数学证明-创新互联
链接URL:http://cdkjz.cn/article/cshcpe.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220