algorithm - 插值搜索有时间复杂度还是空间复杂度？

Question

我对插值空间和时间复杂度做了一些研究，但没有找到任何结论性的结果。 所以我的问题是插值搜索的时间和空间复杂度是多少？ 我知道它类似于二进制搜索，但它肯定没有与二进制搜索算法相同的时间和空间复杂度吗？ 预先感谢您的帮助。

Answer 1

是的，是known .

---

时间

平均情况:log(log(n))

最坏情况:O(n)

空间

您只需要将索引存储在列表中以进行搜索，因此它是 O(1)。