3.1.40

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

顺序查找平均需要进行 $ N/2 $ 次比较,二分查找则是 $ \lg N $ 次。
列出方程可以解出 N 的大小
$$
\begin {eqnarray*}
1000 \log_2 N &=& N / 2 \\
\log_2 N &=& N / 2000\\
\frac{\ln N}{\ln 2} &=& N/2000 \\
N &=& e^{\frac{\ln 2}{2000}N}\\
1 &=& Ne^{-\frac{\ln 2}{2000}N}\\
N_1 = e^{-W(-\frac{\ln 2}{2000})}=1 & & N_2= e^{-W_{-1}(-\frac{\ln 2}{2000})}=29718\ \\
\end {eqnarray*}
$$
这个方程是一个超越方程,最后的结果中出现了朗伯 W 函数。
同理可以求得 10000 倍的 N=369939。

实验结果如下:

由于存在缓存优化,每次比较的耗时并不相同。
因此实际耗时并未达到预期,但比较次数是符合预期的。

另请参阅

朗伯 W 函数-维基百科

上一题 下一题