倍增算法 - (sunznx) 振翅飞翔
25 September 2019

倍增算法是二分的一种。由于我也是刚入门,本文顶多算是个人的备忘录,请多多指教。

倍增的入门使用场景

设一个数组 arr,数组的每个元素都大于 0,给定一个数 T,求最大的 i,使得 sum(0, i) >= T

朴素算法:

function query($T)
{
    $ans = 0;
    $sum = 0;
    foreach ($this->arr as $i => $num) {
        $sum += $num;
        if ($sum <= $T) {
            $ans = $i;
        } else {
            break;
        }
    }
    return $ans;
}

朴素算法的运行效率是 O(n),该算法的缺点是当 query 执行很多次的时候,效率自然会下降。
下面是一个含有 50000 数字数组,随机查询 500000 次

 (result1)
 8.81s user 0.67s system 98% cpu 9.660 total

假如我们将数组 arr 的前缀先算出来,再利用二分初始化,那么便可以在 O(logn) 时间内得到结果

二分算法

function prework()
{
    $sum = 0;
    foreach ($this->arr as $i => $num) {
        $sum += $num;
        $this->s[$i] = $sum;
    }
}

function query($T)
{
    $ans = 0;

    $l = 0;
    $r = count($this->s) - 1;

    while ($l <= $r) {
        $mid = (int)(($l + $r) / 2);

        if ($this->s[$mid] > $T) {
            $r = $mid-1;
        } else {
            $l = $mid + 1;
            $ans = $mid;
        }
    }

    return $ans;
}

对二分算法,我们同样进行测试,数组元素有 50000 个,随机查询 500000 次

 (result2)
 3.29s user 0.66s system 98% cpu 4.003 total

对比 上面的结果 可以发现效率有一定的提升。

O(n) 的反击

二分的缺点是什么?假设我们我们每次查询的 T 都很小,例如 query(random_int(0, 999)) ,再执行上面的查询
朴素查询的结果:

 (result3)
 1.52s user 0.61s system 97% cpu 2.176 total

二分的结果:

 (result4)
 3.04s user 0.62s system 98% cpu 3.732 total

可以发现,朴素查询的效率反而更快,因为它只需要遍历前面几个数字就找到答案了

倍增算法

倍增算法的思路是按 1, 2, 4, 8, 16, 32, ... 的增长区间开始取数判断是否满足条件,如果满足继续增长,否则,缩小区间

function query($T)
{
    $r = count($this->s) - 1;

    $k = 0;
    $p = 1;

    while ($p != 0) {
        if ($k + $p <= $r && $this->s[$k + $p] <= $T) {
            $k = $k + $p;
            $p = $p * 2;
        } else {
            $p = (int) ($p / 2);
        }
    }

    return $k;
}

可见,倍增算法相比二分可以做到 “更稳定” 的二分

区间最值的倍增 – st 算法

st 算法用于求区间最值上,思路如下:
f(i, j) 表示区间 [i, i+2j-1] 的最大值,即从 i 开始的 2j 个数的最大值,可以得到 f(i, 0)=arr[i] ,j 的最大值为 (int)(log(n)/log(2))

f(i, j) = max(f(i, j-1), f(i+2(j-1), j-1))

设数组个数为 n ,则计算过程中, i 的值最大为 n-(2j)

function prework()
{
    $n = count($this->arr);

    for ($i = 0; $i < $n; $i++) {
        $this->f[$i][0] = $this->arr[$i];
    }

    $t = (int)(log($n) / log(2));
    for ($j = 1; $j <= $t; $j++) {
        for ($i = 0; $i < $n - (1<<$j) + 1; $i++) {
            $this->f[$i][$j] = max(
                $this->f[$i][$j-1],
                $this->f[$i + (1<<($j-1))][$j-1]
            );
        }
    }
}

计算区间 [l, r] 最值的时候,先计算出 k = (int)(log(r-l+1) / log(2)) ,其中 (r-l+1) 为区间长度, 2k 则是这个区间刚好大于或等于的 2 的 k 次幂, 2(k+1) 一定是大于区间长度 (r-1+1) 的。例如:
区间长度为 9,则 k 为 3,2k 为 8,2(k+1) 为 16

把区间 [l, r] 分成两段,长度都是 2k ,那么两段加起来的长度就是 2(k+1) ,以为着这两端一定能覆盖整个区间(还可能有重叠,忽略重叠部分),计算出这两段的最值就能求出原区间的最值。

function query($l, $r)
{
    $k = (int)(log($r-$l+1) / log(2));
    return max(
        $this->f[$l][$k],
        $this->f[$r - (1 << $k) + 1][$k]
    );
}

参考

《算法竞赛 – 进阶指南》