二分

Published: by Creative Commons Licence

  • Tags:

三分算法

假设存在一个定义域和值域均为$\mathbb{R}$的连续下凸函数$f$,要求求函数$f$的极小值。

一般的严格单调函数,我们可以利用二分查找法,以理论最优时间复杂度$O(\log_2D)$,其中D表示函数的定义域大小。

考虑到下凸函数的极值点左端为单调减函数,而右端为单调增函数。我们可以将二分转换为三分,即将区间$[l,r]$划分为$[l,ml]$,$[ml,mr]$和$[mr,r]$。其中$ml=l+(r-l)/3$,而$mr=r-(r-l)/3$。

我们考虑三种情况:

  1. 极值点落在$[l,ml]$,这时候一定有$f(ml)\leq f(mr)$,我们可以重置$r=mr$。
  2. 极值点落在$[mr,r]$,这时候一定有$f(ml)\geq f(mr)$,我们可以重置$l=ml$。
  3. 极值点落在$[ml,mr]$,这时候我们可以任意选择重置$l=ml$或$r=mr$的一种。

换言之,我们可以总结为若$f(ml)\leq f(mr)$,则重置$r=mr$,否则重置$l=ml$。

由于每次减少$\frac{1}{3}$的区间,因此时间复杂度为$\log_{1.5}D$。

但是说句实话,三分法要求函数必须为凸函数,而一般问题的难点就是证明函数的凸性。如何保证不存在局部极值点,这是一个很难的问题,当然可以拼运气,但是终究不是好主意。可以选择更加科学的模拟退火算法,其仅需要函数连续,而不要求凸性,尤其在多个维度的情况下,三分并不好写,而模拟退火算法依旧非常好用。

所以为什么要学三分呢,捂脸。。。

二分中的相对和绝对误差

现在很多输出浮点数的题目都会提供两种AC条件,一种是输出与真实结果的绝对误差不超过阈值,一种是输出与真实结果的相对误差不超过阈值。

绝对误差的定义为,预估值为$x$,真实值为$y$,那么绝对误差为$|x-y|$,同理相对误差可以定义为$|\frac{x-y}{y}|$。

之前一直都没太关注相对误差,但是最近在做Atcoder上的一道题的时候踩了坑。

相对误差在输出结果很大的时候会发挥巨大的作用。总所周知双精度浮点型共64位,其中1位用于表示符号,11位表示指数,其余的52位用于表示有效数字。简单换算就可以知道双精度浮点型可以精确表示大概15位十进制整数($2^{10}\approx 10^3$)。

现在考虑一个问题,最终结果为$10^8$,但是要求绝对误差小于$10^{-8}$,这现实吗。事实上尾部的数值由于有效数值不足会被舍去。这就会导致二分的时候,$(l+r)/2$可能会等于$l$或等于$r$,从而导致二分进入死循环。

但是有了相对误差,情况就会大为不同,当输出为$10^8$时,我们可以不需要保留任意小数。

下面考虑相对误差为$t$时,二分左右边界为$l$和$r$时,如何判断是否达到了相对误差阈值,当$l<0<r$的时候,使用绝对误差进行测试,因为这时候不会出现精度问题。如果$l>0$,那么可以利用下面公式检测相对误差:

\[|\frac{y-l}{y}|\leq |\frac{r-l}{y}|\leq |\frac{r-l}{l}|\leq t\\\]

对应的,如果$r<0$,那么可以用下面公式检测相对误差:

\[|\frac{y-l}{y}|\leq |\frac{r-l}{y}|\leq |\frac{r-l}{r}|\leq t\\\]

缝隙二分

以前一直以为二分只能作用在单调函数上,现在发现二分还能作用在非单调函数上查找缝隙。

所谓的缝隙是指这样一个整数$x$,满足$check(x-1)\neq check(x)$。

要执行缝隙二分的前提是,一开始给定的$l$和$r$满足$check(l)\neq check(r)$。

在执行缝隙而二分的过程,利用$l$和$r$算出$mid=(l+r)/2$后,如果$check(mid)=check(l)$,那么就令$l=mid$,否则令$r=mid$。容易发现这样做始终能保证$check(l)\neq check(r)$。由于区间在不断缩小,因此最终一定能找到一个缝隙。当然我们无法确定找到的是哪个缝隙,但是这不重要。

可以试试Atcoder的这道题目,它就利用了缝隙二分的方法。