来一个简单的问题——找末项

2020-08-07 本文已影响0人離塵真心

有若干盒子排成一列，已知第1个盒子不是空的，从第1个到第 $n$ 个都不是空的，但是从此往后的盒子都是空的。但是，打开每个盒子看是需要一定时间的，比如需要时长 $t$ 。已知 $n<N$ ，请问如何能够在最短的时间内找到这个盒子？

思路一：逐项法

也就是逐项去看盒子是不是空的。这种情形下，需要看 $n$ 次。

思路二：二分法

举个简单的例子，取 $N=10$ 。

$\frac{1+10}{2}=5.5$ ，四舍五入至6，看第6个盒子是不是空的。结果一看，是空的，则 $n$ 介于1~6之间。

$\frac{1+6}{2}=3.5$ ，四舍五入至4，看第4个盒子是不是空的。结果一看，不是空的，则 $n$ 介于4~6之间。

$\frac{4+6}{2}=5$ ，看第5个盒子是不是空的。结果一看，不是空的。

现在已知第5个盒子不是空的，第6个盒子是空的，则 $n=5$ 。

通过这个例子可以大概感觉到，看多少次，是看从n除以多少次2以后，能达到或小于1。即求解 $\frac{n}{2^x}=1$ ，解得 $x=\log_2 n$ ，也就是大概需要 $\log_2 n$ 次。我们知道，当 $n \geq 1$ 时，总有 $\log_2 n < n$ 。因此，二分法比逐项法要好。

思路三

难道就没有别的方法了吗？试试嘛。比如，先看第100、200、300、……个盒子是不是空的。照这个顺序去看，发现的第一个空盒子，记为 $n_0$ ，比如是600，则说明最后一个非空的盒子是在第500个和第600个之间。然后再用二分法，在500~600的范围内找。

那么问题来了，你为什么要设定公差是100，而不是200，即先看第200、400、600、……个盒子？

先找一个最优的公差 $x$ 吧，然后再看看这是不是比二分法要快。

记这种方法需要看 $y$ 次盒子。则有

$y \leq \frac{n+1}{x}+\log_2 x +1$

记右式为 $w$ ，则 $w=\frac{n+1}{x}+\log_2 x +1$ 。

$w'=-\frac{n+1}{x} \left( \frac{1}{x} - \frac{1}{(n+1)\ln2} \right)$

$1/x$	$0$	$(0,\frac{1}{(n+1)\ln2})$	$\frac{1}{(n+1)\ln2}$	$(\frac{1}{(n+1)\ln2}, + \infty)$
$x$	$+ \infty$	$((n+1)\ln2,+ \infty)$	$(n+1)\ln2$	$(0,(n+1)\ln2)$
$w'$	0	+	0	-
$w$		单调增加	$w^*$	单调减少

因此当 $x=(n+1) \ln 2$ 时， $w$ 取得最小值 $w^*=\frac{1+\ln[2(n+1)\ln 2]}{\ln2}$ 。

与二分法的 $\log_2 N=\frac{\ln N}{\ln 2}$ 相减得：

$w^*-\log_2 N=\frac{1}{\ln2} \left[ \ln\left( 2e(n+1)\ln2 \right) -\ln N \right]$

令 $w^*-\log_2 N<0$ ，则解得 $n< \frac{N}{2e\ln 2}-1$
其中 $\frac{1}{2e \ln 2} \approx 0.2654$ 。

也就是说，当最后一个盒子的序号 $n$ 大致小于 $N$ 的四分之一时，思路三更快，否则是二分法更快。

总结

这思路三的方法有什么用？

反正我是用它找Excel中某一张表的最后一行，反正比自带的Sheet.UseRange.Rows.Count要快。

上一篇下一篇

猜你喜欢

热点阅读