Divide and Conquer Algorithm - tenji/ks Wiki

分治算法

一、基本概念

在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)……

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于 n 个元素的排序问题,当 n = 1 时,不需任何计算。n = 2 时,只要作一次比较即可排好序。n = 3 时只要作 3 次比较即可,…。而当 n 较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。

二、基本思想及策略

分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

分治策略是:对于一个规模为 n 的问题,若该问题可以容易地解决(比如说规模 n 较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

如果原问题可分割成 k 个子问题,1 < k ≤ n,且这些子问题都可解并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。

三、分治法使用的情况

分治法所能解决的问题一般具有以下几个特征:

分治法所能解决的问题一般具有以下几个特征:

  1. 该问题的规模缩小到一定的程度就可以容易地解决
  2. 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质
  3. 利用该问题分解出的子问题的解可以合并为该问题的解;
  4. 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题

第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;

第二条特征是应用分治法的前提它也是大多数问题可以满足的,此特征反映了递归思想的应用;

第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑用贪心法或动态规划法

第四条特征涉及到分治法的效率,如果各子问题是不独立的则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好

四、分治法的基本步骤

分治法在每一层递归上都有三个步骤:

step1 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;

step2 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;

step3 合并:将各个子问题的解合并为原问题的解。

它的一般的算法设计模式如下:

    Divide-and-Conquer(P)

    1. if |P|≤n0

    2. then return(ADHOC(P))

    3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk

    4. for i←1 to k

    5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi

    6. T ← MERGE(y1,y2,...,yk) △ 合并子问题

    7. return(T)

其中 |P| 表示问题 P 的规模;n0 为一阈值,表示当问题 P 的规模不超过 n0 时,问题已容易直接解出,不必再继续分解。ADHOC(P) 是该分治法中的基本子算法,用于直接解小规模的问题 P。因此,当 P 的规模不超过 n0 时直接用算法 ADHOC(P) 求解。算法 MERGE(y1, y2, ..., yk) 是该分治法中的合并子算法,用于将 P 的子问题 P1, P2, ..., Pk 的相应的解y1, y2, ..., yk合并为P的解。

五、分治法的复杂性分析

一个分治法将规模为n的问题分成 k 个规模为 n/m 的子问题去解。设分解阀值 n0 = 1,且 adhoc 解规模为 1 的问题耗费 1 个单位时间。再设将原问题分解为 k 个子问题以及用 merge 将 k 个子问题的解合并为原问题的解需用 f(n) 个单位时间。用 T(n) 表示该分治法解规模为 |P| = n 的问题所需的计算时间,则有:

T(n) = k T(n/m) + f(n)

通过迭代法求得方程的解:

递归方程及其解只给出 n 等于 m 的方幂时 T(n) 的值,但是如果认为 T(n) 足够平滑,那么由 n 等于 m 的方幂时 T(n) 的值可以估计 T(n) 的增长速度。通常假定 T(n) 是单调上升的,从而当 mi ≤ n < mi + 1 时,T(mi) ≤ T(n) < T(mi+1)。

六、算法流程

实际上就是类似于数学归纳法,找到解决本问题的求解方程公式,然后根据方程公式设计递归程序。

  1. 一定是先找到最小问题规模时的求解方法;
  2. 然后考虑随着问题规模增大时的求解方法;
  3. 找到求解的递归函数式后(各种规模或因子),设计递归程序即可。

七、分析样例

7.1 题目描述(395. 至少有 K 个重复字符的最长子串

给你一个字符串 s 和一个整数 k ,请你找出 s 中的最长子串, 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

示例 1:

输入:s = "aaabb", k = 3
输出:3
解释:最长子串为 "aaa" ,其中 'a' 重复了 3 次。

示例 2:

输入:s = "ababbc", k = 2
输出:5
解释:最长子串为 "ababb" ,其中 'a' 重复了 2 次, 'b' 重复了 3 次。

提示:

  • 1 <= s.length <= 104
  • s 仅由小写英文字母组成
  • 1 <= k <= 105

7.2 题目分析

对于字符串 ss,如果存在某个字符 ch,它的出现次数大于 0 且小于 k,则任何包含 ch 的子串都不可能满足要求。也就是说,我们将字符串按照 ch 切分成若干段,则满足要求的最长子串一定出现在某个被切分的段内,而不能跨越一个或多个段。因此,可以考虑分治的方式求解本题。

7.3 代码实现

public int longestSubstring(String s, int k) {
    /*
    分治算法:

    对于字符串 ss,如果存在某个字符 ch,它的出现次数大于 0 且小于 k,则任何包含 ch 的子串都不可能满足要求。
    也就是说,我们将字符串按照 ch 切分成若干段,则满足要求的最长子串一定出现在某个被切分的段内,而不能跨越一个或多个段。
    因此,可以考虑分治的方式求解本题。

     */

    if (s.length() < k) {
        return 0;
    }

    int result = 0;

    // 保存每个字母出现的频率
    HashMap<Character, Integer> counter = new HashMap<>();

    // 统计该字符串中每个字母出现的频率
    for (int i = 0; i < s.toCharArray().length; i++) {
        Character character = s.toCharArray()[i];

        counter.put(character, counter.getOrDefault(character, 0) + 1);
    }

    for (Map.Entry<Character, Integer> entry : counter.entrySet()) {
        Character character = entry.getKey();
        Integer num = entry.getValue();

        if (num < k) {
            // 如果存在某个字符的出现频率小于 k,则按照此字符分割该字符串,递归计算子字符串中满足条件的最大长度
            String[] strArr = s.split(character.toString());
            for (int i = 0; i < strArr.length; i++) {
                result = Math.max(result, longestSubstring(strArr[i], k));
            }
            return result;
        }
    }

    // 该字符串包含的所有字符出现频率都大于 k,直接返回该字符串长度即可
    return s.length();
}

八、Leetcode 题目

九、参考链接