algorithm - 为什么在插值搜索中每次比较后列表长度都会减少到 sqrt(n)？

Question

根据我正在阅读的书，插值搜索在平均情况下需要 O(loglogn)。
本书假定每次比较都会将列表的长度从 n 减少到 sqrt(n)。好吧，根据这个假设，计算出 O(loglogn) 并不难。
然而，这本书并没有更多地谈论这个假设，只是说这是正确的。

问题:谁能解释一下为什么这是真的？

Answer 1

这取决于输入是均匀分布的(没有这样的假设，O(log n) 是理论上你能做的最好的，即二分查找是最优的)。对于均匀分布，方差约为 sqrt(n)，并且在预期情况下，每次迭代都在目标方差范围内。因此，正如您所说，搜索空间在每次迭代中从 n -> sqrt(n) 开始。