3.1.41 #

解答 #

英文版描述为 1, 2, and 10 times faster。

即一样快，快一倍和快十倍（一个例子）。

和上题类似，也是解超越方程。

插值查找的平均查找次数为 $\lg(\lg(N))$。

可以解得 N = 1, 4, 58。

实验结果如下：

由于 N 太小，可以看到插值查找的运行时间几乎没有变化。