插值搜索有时间或空间复杂度吗？

Question

我对插值、空间和时间复杂度做了一些研究，但没有得到任何结论。那么，我的问题是，插值搜索的时间和空间复杂度是多少？我知道它类似于二进制搜索，但是它不具有二进制搜索算法的时间和空间复杂度吗？提前谢谢你的帮助。

Answer 1

是的，是已知。

时间

平均病例：log(log(n))

最坏情况：O(n)

空格

您只需要将索引存储在列表中供搜索，所以它是O(1)。