Hao*_*hun 10 algorithm math complexity-theory
根据我正在阅读的书,插值搜索采用O(loglogn)平均情况.
本书假定每个比较减少从列表的长度n来sqrt(n).嗯,要弄清楚O(loglogn)给定的这个假设并不困难.
然而,这本书没有更多地谈论这个假设,只是它说这是正确的.
问题:有人可以解释为什么这是真的吗？
它取决于输入是否均匀分布(没有这样的假设,O(log n)是理论上你能做到的最好的,即二进制搜索是最优的).在均匀分布的情况下,方差在sqrt(n)附近,并且在预期情况下,每次迭代都在目标的方差内.因此,正如您所说,搜索空间在每次迭代时都来自n - > sqrt(n).