3.1.41

3.1.41 #

解答 #

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

即一样快,快一倍和快十倍(一个例子)。

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

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

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

实验结果如下:

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