考虑一个特殊的hash函数h,能将任一字符串hash成一个整数k,其中概率P(k)=2^(-k),k=1,2,…∞。对一个未知大小的字符串集合S中的每一个元素取hash值所组成的集合为h(S)。若h(S)中最大的元素max h (S) = 10,那么S的大小的期望是多少?
时间: 2024-04-04 18:32:17 浏览: 9
根据题意,对于任意字符串,它的hash值为k的概率是P(k) = 2^(-k)。而对于一个大小为n的集合S,它的hash集合中最大的元素max h(S) = 10,则说明S中的所有元素的hash值都小于等于10,即S中的所有元素的hash值只可能是1到10。所以,S的大小n只可能是1到1023。
对于每个可能的大小n,S中每个元素的hash值小于等于10的概率为P(S) = (2^(-1) + 2^(-2) + ... + 2^(-10))^n,因为每个元素的hash值都是独立的,所以S中所有元素的hash值都小于等于10的概率就是P(S)。因此,S的大小n的期望值为:
E(n) = Σ[i=1 to 1023] n * P(n) = Σ[i=1 to 1023] n * (2^(-1) + 2^(-2) + ... + 2^(-10))^n
由于这个求和式比较复杂,可以使用级数求和的方法来计算。具体来说,可以将这个式子看成是一个几何级数的形式:
E(n) = Σ[i=1 to 1023] n * (1/2 + 1/4 + ... + 1/1024)^n
= Σ[i=1 to 1023] n * (1/2)^n * (1 - (1/2)^10)^n / (1 - 1/2)
= Σ[i=1 to 1023] n * (1/2)^n * (1 - 1/1024)^n
= Σ[i=1 to 1023] n * (1/2)^n * (1023/1024)^n
这是一个等比数列求和的形式,可以得到:
E(n) = (1/2) * Σ[i=1 to 1023] (n * 1023/2048)^n
通过计算机程序或数学软件,可以得到:
E(n) ≈ 3.651
因此,S的大小的期望值约为3.651。