算法基础算法

倍增法

字数统计: 1.1k字   |   阅读时长: 4分
, ,

摘要: 倍增法原理、代码模板、例题与应用场景

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

$1 倍增法算法思想

在递推状态的时候，只递推状态空间中 2 的幂次，当需要求其它位置的时候，利用以下性质，可以用此前求过的 2 的幂次上的状态现算出来：

1
任意整数可以表示成若干个 2 的幂次的和

这种算法称为倍增法。倍增法与二进制划分结合可以降低很多问题的时间和空间复杂度，例如快速幂，倍增优化DP。

模型问题1

长度为 $N$ 的数列 $A[0..N-1]$，处理在线 $Q$ 个查询：每次给定一个整数 $T$，求最大的 $k$ 使得 $A$ 中前 $k$ 个数的和 $\sum\limits_{i=0}\limits^{k-1}A[i] \leq T$，其中 $0 \leq T \leq \sum\limits_{i=0}\limits^{N-1}A[i]$。

算法1

每次询问都对 $k$ 进行 $O(N)$ 的枚举，总 $O(NQ)$。

算法2

预处理前缀和 S[i] := A[0..i-1]，每次查询，二分 k，通过比较 S[k] 和 T 的关系调整 K 的上下界。总 $O(N+Q\log N)$。

算法3：倍增法

1
2
3
4
5
6
7
8
p = 1, k = 0, sum = 0
求 A[k..k+p-1] 的和(共p个数), 结果为 S[k + p] - S[k]
若 sum + S[k + p] - S[k] <= T，则
    累加上这 p 个数的和，然后将 p 的跨度增长一倍
    sum += S[k + p] - S[k], k += p, p *= 2
若 sum + S[k + p] - S[k] > T，则
    不累加，p /= 2 再试
当 p 为 0 时，k 为答案

倍增法

模型问题2

这是一个交互问题。

您有一个升序整数数组，其长度未知。您没有访问数组的权限，但是可以使用 ArrayReader 接口访问它。你可以调用 ArrayReader.get(i):

返回数组第ith个索引(0-indexed)处的值(即 secret[i])，或者如果 i 超出了数组的边界，则返回 $2^{31} - 1$

你也会得到一个整数 target。

如果存在 secret[k] == target，请返回索引 k 的值；否则返回 -1

你必须写一个时间复杂度为 $O(\log n)$ 的算法。

提示：

1
2
3
1 <= secret.length <= 1e4
-1e4 <= secret[i], target <= 1e4
secret 严格递增

示例 1：
输入: secret = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 存在在 nums 中，下标为 4

示例 2：
输入: secret = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不在数组中所以返回 -1

算法：倍增法

由于数组有序，可以考虑二分的方法。但这里数组的长度未知，二分的算法不好实现。但可以通过倍增法处理。

从数组最左边 A[0] 往右走，每一步走 step，也就是上一步访问 A[i]，走一步之后访问 A[i+step]。初始时 step = 1。

假设当前访问了 i 位置的数据 A[i]，并且 A[i] < target，此时我们考虑下一个数据 A[i + step]，

  • 如果当前访问的 A[i + step] == target 那么就找到了；
  • 如果 A[i + step] < target，那么 target 的位置在 i + step 的右边，向右走 i += step，然后将 step 翻倍；
  • 如果 A[i + step] > target，那么 target 的位置在 i + step 的左边，不能向右走，而是将 step 减半。

代码 (C++, 模板)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int search(const ArrayReader& reader, int target) {
        int i = 0, step = 1;
        if(reader.get(0) == target)
            return 0;
        while(step > 0)
        {
            int cur = reader.get(i + step);
            if(cur == target)
                return i + step;
            else if(cur < target)
            {
                i += step;
                step *= 2;
            }
            else
                step /= 2;
        }
        return -1;
    }
};

$2 倍增法应用场景

1. 快速幂

参考文章：

2. LCA

参考文章：

3. RMQ

参考文章：

4. 倍增优化DP

参考文章：

5. 多重背包

参考文章：

6. 后缀数组

参考文章：

$7 理想跳表

参考文章：

Share