算法基础算法

分治

字数统计: 2.7k字   |   阅读时长: 11分
, ,

$0 主定理

分治的过程

  • Divide(分解): 将原问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小
  • Conquer(解决): 递归地求解子问题，如果子问题的规模足够小，停止递归，直接解决
  • Combine(合并): 将子问题的解组合为原问题的解

算法分析符号

  • $O$: 渐进上界
  • $o$: 渐进小于
  • $\Omega$: 渐进下界
  • $\Theta$: 既是渐进上界又是渐进下界

递归式

递归式就是一个等式或不等式，通过更小的输入上的函数值来描述一个函数。例如归并排序的递归式：

求解得 $T(N) = \Theta(N\log N)$

递归式的形式

一个递归算法可以将问题分成规模不等的子问题，例如分成 $1/3$ 和 $2/3$ 两部分。如果分解和合并的步骤都是线性的，则每次递归调用将花费线性时间加上下一层的两次递归调用的时间。递归式：$T(N) = T(2N/3) + T(N/3) + \Theta(N)$

一个递归算法分成的子问题规模还可以不是原问题规模的一个比例，例如比原问题少一个元素，每次递归调用将花费常数时间再加上下一层递归调用的时间，插入排序就是这种情况。递归式：$T(N) = T(N - 1) + \Theta(1)$

一个递归算法将原问题分成若干子问题，还可以只求解其中一个子问题，例如二分算法就是这种情况。每次递归调用将花费常数时间再加上下一层递归调用的时间。递归式：$T(N) = T(N/2) + \Theta(1)$

后两种情况都可以视为减治法，即拆分问题后只需要递归求解一个子问题即可得原问题的解。

递归式的求解

  1. 代入法：猜测是个界，然后用数学法归纳法证明这个界是正确的
  2. 递归树法：将递归式转换成一棵树，其节点表示不同层次的递归调用产生的代价，然后采用边界和技术(techniques for bounding summations)求解。
  3. 主方法：可以求解形如 $T(N) = aT(N/b) + f(N)$ 的递归式的界，这个递归式表示的是这样一种分治算法：生成 a 个子问题，每个子问题规模是原问题规模的 $N/b$， 分解和合并的步骤花费时间 $f(N)$

代入法很简洁，但是好的猜测很难。递归树很适合用于生成好的猜测，之后再用代入法验证该猜测，但生成好的猜测时，需要忍受地点不精确，因为之后才会验证该猜测是否正确。

如果在画递归树和代价求和时非常仔细，就可以用递归树直接证明解是否正确。主方法的基础定理就是使用递归树证明的。

更多细节参考《算法导论》第一部分第4章

不等式型递归式

递归式描述了 $T(N)$ 的一个上界，用 $O$ 而不是 $\Theta$ 描述其解。

主方法求解递归式

主方法为求解形如 $T(N) = aT(N/b) + f(N)$ 的递归式的界提供了一种定式化的方法

这个递归式表示的是这样一种分治算法：生成 a 个子问题，每个子问题规模是原问题规模的 $N/b$， 分解和合并的步骤花费时间 $f(N)$

例如描述矩阵乘法 Strassen 算法的递归式中: a = 7, b = 2, $f(N) = \Theta(N^{2})$

主定理

主方法依赖于主定理

令 $a \geq 1, b > 1$ 为常数，$f(N)$ 为一个函数，$T(N)$ 是定义在非负整数上的递归式 $T(N) = aT(N/b) + f(N)$，其中将 $N/b$ 解释为 $\lfloor N/b \rfloor$ 或 $\lceil N/b \rceil$ 则 $T(N)$ 有如下渐进界

  1. 若对某个常数 $\epsilon > 0$ 有 $f(N) = O(N^{\log_{b}a-\epsilon})$，则 $T(N) = \Theta(N^{\log_{b}a})$
  2. 若 $f(N) = \Theta(N^{\log_{b}a})$，则 $T(N) = \Theta(N^{\log_{b}a}\log N)$
  3. 若对某个常数 $\epsilon > 0$ 有 $f(N) = \Omega(N^{\log_{b}a-\epsilon})$，且对某个常数 $c < 1$ 和所有足够大的 N 有 $af(N/b) \leq cf(N)$，则 $T(N) = \Theta(f(N))$

定理三种情况的含义是比较 $f(N)$ 和 $N^{\log_{b}a}$，情况 1~3 分别对应上述比较的渐进小于，渐进等于，渐进大于。

这三种情况并未覆盖 $f(N)$ 的所有可能性，例如 $f(N)$ 小于 $N^{\log_{b}a}$，但并不是渐进小于。未覆盖的情况，不能使用主方法求解递归式。

证明和使用方法参考《算法导论》第一部分第4章

$1 二分分治

53. 最大子序和

分治法的意义：可以处理动态询问 [i, j] 的最大子段和，可以把分治过程中子区间的最大子段和维护在线段树上，线段树上隐含了分治算法

[线段树-分治+区间合并]区间最大子段和有三种情况：

  1. 左子树最大子段和
  2. 右子树最大子段和
  3. 左子树的最大后缀和 + 右子树的最大前缀和

23. 合并K个升序链表

合并 K 个链表问题，分解为两个合并 K/2 个链表的问题

  • 分解：将 K 个链表平均分成两份
  • 解决：当 K = 1 时可以直接解决，即返回该链表
  • 合并：合并 2 个链表的问题

…

169. 多数元素

  • 分解：将数组分为左右两部分
  • 解决：当数组长度为 1 时，可以直接解决，即众数为数组中的一个元素
  • 合并：左边的众数为 x，右边的众数为 y，若 x 和 y 不同，则需要遍历区间决定谁才是整个区间上真正的众数

算法的正确性依赖多数元素的个数大于数组元素个数的一半这个条件。

力扣169,299-摩尔投票

932. 漂亮数组

对于问题 A[l..r]：

  • 分解：将 A[l+2i] 放进左半边，将 A[l+2i+1] 放进右半边
  • 解决：当 r = l 时，可以直接解决，即返回 A[l]
  • 合并：将左边的结果 left 和右边结果 right 合并

【分治难题】力扣932-漂亮数组

751. IP 到 CIDR

【分治难题】力扣751-IP到CIDR

参考

$2 四分分治

1274. 矩形内船只的数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    //
    //          [x2, y2]
    //
    // [x1, y1]
    int countShips(Sea sea, vector<int> topRight, vector<int> bottomLeft) {
        int x1 = bottomLeft[0], x2 = topRight[0];
        int y1 = bottomLeft[1], y2 = topRight[1];
        return _countShips(sea, x1, x2, y1, y2);
    }

private:
    int _countShips(Sea sea, int x1, int x2, int y1, int y2)
    {
        // cout << x1 << " " << x2 << " " << y1 << " " << y2 << endl;
        // 调用方保证 x1 <= x2, y1 <= y2
        if(!sea.hasShips(vector<int>({x2, y2}), vector<int>({x1, y1})))
            return 0;
        if(x1 == x2 && y1 == y2)
            return 1;

        int midx = (x1 + x2) / 2;
        int midy = (y1 + y2) / 2;

        int topleft = 0;
        int topright = 0;
        int bottomleft = 0;
        int bottomright = 0;
        topleft = _countShips(sea, x1, midx, y1, midy);
        if(y1 < y2)
            topright = _countShips(sea, x1, midx, midy + 1, y2);
        if(x1 < x2)
            bottomleft = _countShips(sea, midx + 1, x2, y1, midy);
        if(x1 < x2 && y1 < y2)
            bottomright = _countShips(sea, midx + 1, x2, midy + 1, y2);
        return topleft + topright + bottomleft + bottomright;
    }
};

参考

$3 CDQ分治

315. 计算右侧小于当前元素的个数

力扣315-索引数组,归并树

参考

$4 相近的场景和概念

(1) 分治与减治

分治需要先得到子问题的解，然后汇总合并后才能出原问题的解，根据主定理，分割子问题时选择中点是时间复杂度最好的。

减治是根据一定依据选择分隔点(可能与参数有关)，先判断原问题的解与哪个子问题有关系，然后只求解有关系的子问题，无关的子问题就舍弃掉不求解了(不一定递归的每一层都有子问题可以舍弃，例如接雨水)。

(2) 分治与搜索

枚举所有区间分隔点的搜索问题

分治：用任意分隔点分割出两个子问题，分别求解后合并都可以出解，而根据主定理，分隔点在中间是最好的

搜索：用任意分隔点分割出两个子问题，分别求解后合并都可以形成一种可行解，目标是要寻找哪个分隔点形成的原问题答案是最好的。

如果对每个分隔点形成的两个子问题的结果增加记忆化，可以形成一种区间DP

241. 为运算表达式设计优先级 / 面试题 08.14. 布尔运算

282. 给表达式添加运算符

1130. 叶值的最小代价生成树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
struct Result
{
    int val; // 节点值
    int sum; // 子树各个节点值之和
    int max_leaf;
    Result(int val, int sum, int max_leaf):val(val),sum(sum),max_leaf(max_leaf){}
};

class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {
        int n = arr.size();
        int sum = 0;
        for(int i: arr)
            sum += i;
        dp = vector<vector<Result>>(n, vector<Result>(n, Result(-1, -1, -1)));
        Result result = solve(arr, 0, n - 1);
        return result.sum - sum;
    }

private:
    vector<vector<Result>> dp;

    Result solve(const vector<int>& arr, int l, int r)
    {
        if(l == r)
            return Result(arr[l], arr[l], arr[l]);
        if(dp[l][r].val != -1)
            return dp[l][r];
        // l < r
        Result result(-1, INT_MAX, -1);
        for(int mid = l; mid < r; ++mid)
        {
            Result left = solve(arr, l, mid);
            Result right = solve(arr, mid + 1, r);
            int val = left.max_leaf * right.max_leaf;
            int max_leaf = max(left.max_leaf, right.max_leaf);
            int sum = val + left.sum + right.sum;
            if(sum < result.sum)
            {
                result.val = val;
                result.max_leaf = max_leaf;
                result.sum = sum;
            }
        }
        return dp[l][r] = result;
    }
};
Share