Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
我参加了高频交易面试,他们问我数据结构的所有数学方面的一个问题是:负载因子 a=1-1/(sqrt(n)logn),搜索不成功的时间是多少?仅使用“n”陈述答案
随着增加,该术语1-1/(sqrt(n)*log(n))接近 1.0 。n当 时n==10,值为 0.9048。当 时n==1000000,值为 0.9999。(我正在使用对数基数 2。)
1-1/(sqrt(n)*log(n))
n
n==10
n==1000000
使用完整的哈希表(负载因子为 1.0 的含义)和开放式寻址,您必须检查每个项目。所以搜索不成功的时间是 O(n)。