扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
《算法导论》中关于链式哈希命中查找运行时间数学证明，一上来就给出公式没看明白，在网上搜了一圈没找到解答心中疑问的文字，于是写下这篇。
题目是计算在链式哈希表中，在均匀散列的情况下，命中查找的运行时间。
分析：命中查找的运行时间，就是一个键数目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 = ∑
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 + α)
■
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网