没有空单元：需要插入多少对象？ 先考虑一个“子问题”：使得被占单元数从达到-1增加到达 到i,需要插入多少对象（期望）？ E(X1)=1,E(X2)=k/(k-1),. In general,we have that Xi counts the number of trials until success in an independent trials process with probability of success(k-i+1)/k,and thus, the expected number of steps until the first success is k/(k-i+1),which is the expected value of Xi. E(X)= w名斤宫-=点空 Θ(k logk) 给你一点感觉： k=10000,这个值大约是98000。没有空单元：需要插入多少对象？ 先考虑一个“子问题”：使得被占单元数从达到 i-1 增加到达 到 i, 需要插入多少对象（期望）？ , , …… 给你一点感觉： 当k=10000, 这个值大约是98000