如何求最小值（二）

· · 算法·理论

书接上文。恭喜本文由休闲娱乐升级为算法理论。

考虑把比较器换成给定 u 和序列 v_i，一次性返回 v_i 中有哪些数比 u 小。序列最大长度为 m。

可以发现此算法的比较次数更新为：

T(n)=T(\frac{cn}{k})+T(k,m)+(n-k)/m+1

其中 c 是随机算法导致的期望上的常数。

取 k=\sqrt{n}，递归树第一层代价起到支配作用，所以有：

T(n)=O\left(\dfrac{n}{m}+\log n\right)

其中 \log n 一项为整棵递归树的大小。

关于最优的比较次数：\frac{n/k}{m} + \frac{ck}{m} \ge 2\sqrt{ \frac{n/k}{m} \cdot \frac{ck}{m} } = \frac{2\sqrt{c}}{m}\sqrt{n}

当且仅当 \frac{n}{k} = ck，即 k = \sqrt{n/c}。

最终最小的比较次数猜测为：

T(n) \approx \frac{n}{m} + \frac{2\sqrt{nc}}{m} + O(\log n)

考虑 m=\sqrt{n}，就只需要 O(\sqrt{n}) 次比较。

本人数学很差，以上推导过程均未严谨验证，若要使用此算法应通过尝试确定最优的 k。

如此，我们就取得了一个在部分极端场景下有一定作用的最小值算法。