divide and conquer algorithm

Basic concepts

In computer science, divide and conquer is a very important algorithm. The literal interpretation is “divide and conquer”, which is to divide a complex problem into two or more identical or similar sub-problems, and then divide the sub-problems into smaller sub-problems… Until the final sub-problem can be simply solved directly, the solution of the original problem is the combination of the solutions of the sub-problems. This technique is the basis of many efficient algorithms, such as sorting algorithms (Quick Sort, Merge Sort), Fourier Transform (Fast Fourier Transform)…

The computation time required for any problem that can be solved by a computer is related to its size. The smaller the size of the problem, the easier it is to solve directly, and the less computation time it takes to solve the problem. For example, for the ordering problem of n elements, when n = 1, no computation is required. When n = 2, you only need to make one comparison to sort the order. When n = 3, you only need to make 3 comparisons,… When n is large, the problem is not so easy to deal with. It is sometimes quite difficult to directly solve a large-scale problem.

Basic Ideas and Strategies

The design idea of the divide and rule method is to divide a big problem that is difficult to solve directly into some smaller-scale identical problems, so that each can be broken and divided and conquered.

The divide-and-conquer strategy is: for a problem of scale n, if the problem can be easily solved (for example, the scale n is small), it will be solved directly, otherwise it will be decomposed into k small-scale sub-problems, which are independent of each other. And in the same form as the original problem, solve these sub-problems recursively, and then combine the solutions of each sub-problem to obtain the solution of the original problem. This algorithm design strategy is called divide and conquer.

If the original problem can be divided into k sub-problems, 1 < k ≤ n, and these sub-problems can be solved and the solutions of these sub-problems can be used to obtain the solutions of the original problem, then this divide-and-conquer method is feasible. The sub-problems generated by the divide-and-conquer method are often smaller modes of the original problem, which provides convenience for the use of recursion technology. In this case, repeated application of the divide-and-conquer method can make the sub-problem consistent with the original problem type but its scale continues to shrink, and finally reduce the sub-problem to the point where it is easy to find its solution directly. This naturally leads to the recursion process. Like a pair of twin brothers, divide and conquer and recursion are often used in algorithm design at the same time, resulting in many efficient algorithms.

Circumstances in which the law of partition applies

The problems that can be solved by the partition and rule method generally have the following characteristics:

1. The problem can be easily solved by reducing the scale to a certain extent

2. The problem can be decomposed into several smaller-scale identical problems, that is, the problem has optimal substructure properties.

3. The solutions of the sub-problems decomposed by the problem can be combined into the solutions of the problem;

4. The sub-problems decomposed by this problem are independent of each other, that is, there are no common sub-sub-problems among the sub-problems.

The first feature is that most problems can be satisfied, because the computational complexity of the problem generally increases with the increase of the problem scale;

** The second feature is the premise of applying the divide and rule method ** It is also satisfying for most problems, and this feature reflects the application of recursion thinking;,

** The third feature is the key, whether to use the divide and rule method depends entirely on whether the problem has the third feature **, if ** has the first and second features, but does not have the third feature, you can Consider using the greedy method or the Dynamic Programming method **.

** The fourth feature involves the efficiency of the partition and rule method **. If each sub-problem is not independent, the partition and rule method has to do a lot of unnecessary work and repeatedly solve the common sub-problems. At this time, although the partition and rule method is available, but ** Dynamic Programming is generally better **.

Divide and conquer and Dynamic Programming have similarities and differences. Let’s look at the following two definitions.

Optimal substructure: If an optimal solution of a problem contains the optimal solution of a subproblem, then the problem has an optimal substructure.

Overlapping subproblems: The recursion algorithm used to solve the original problem repeatedly solves the same subproblem, rather than always generating new subproblems. For two subproblems, if they are indeed the same subproblem, but only appear as subproblems of different problems, they overlap.

When sub-problems are independent of each other, divide and conquer can be used and only. Dynamic Programming is a better algorithm when there are overlapping sub-problems. In a word, divide and conquer - each sub-problem is independent; Dynamic Programming - each sub-problem overlaps.

Introduction to Algorithms:

The Basic Steps of Partition

The divide-and-conquer method has three steps at each level of recursion:

Step 1 Decomposition: Decompose the original problem into several small-scale, independent sub-problems with the same form as the original problem;

Step2 solution: If the sub-problem is small and easy to solve, solve it directly, otherwise solve each sub-problem recursion

Step 3 Merge: Merge the solutions of each sub-problem into the solution of the original problem.

Its general algorithm Design pattern is as follows:

Divide-and-Conquer(P)

　　1. if |P|≤n0

　　2. then return(ADHOC(P))

　　3. Decompose P into smaller subproblems P1, P2,..., Pk

　　4. for i←1 to k

　　5. do yi ← Divideo-and-Conquer (Pi) Δrecursion solution Pi

　　6. T ← MERGE (y1, y2,..., yk) ΔMerge subproblems

　　7. return(T)

　　Where | P | represents the size of the problem P; n0 is a threshold value, which means that when the size of the problem P does not exceed n0, the problem is easy to be solved directly without further decomposition. ADHOC (P) is the basic sub-algorithm in the divide-and-conquer method, which is used to directly solve small-scale problems P. Therefore, when the scale of P does not exceed n0, the algorithm ADHOC (P) is directly used to solve it. The algorithm MERGE (y1, y2,..., yk) is a merging subalgorithm in the divide-and-conquer method, used to merge the corresponding solutions y1, y2,..., yk of the subproblems P1, P2,..., Pk of P into the solution of P.

Merge sort

//First look at the function body, the part that implements the split
void mergesort(int a[],int n,int left,int right)
{
    if(left+1<right)
    {
        int mid=(left+right)/2;
        mergesort(a,n,left,mid);
        mergesort(a,n,mid,right);
        merge(a,n,left,mid,right);
    }
}
Now let's write our own merge function!
//L, R are auxiliary arrays!
void merge(int a[],int n,int left,int mid,int right)
{
    int n1=mid-left,n2=right-mid;
    for(int i=0;i<n1;i++)
        L [i] = a [left + i];//store the left sequence
    for(int i=0;i<n2;i++)
        R [i] = a [mid + i];//store the right sequence
    L[n1]=R[n2]=INF;
    int i=0,j=0;
    for(int k=left;k<right;k++)//合并
    {
        if(L[i]<=R[j])
            a[k]=L[i++];
        else
            a[k]=R[j++];
    }
}

Divide and conquer example

Link to question and answer: https://leetcode-cn.com/problems/maximum-subarray/

For an interval [l, r], we can maintain four quantities:

LSum represents the sum of the largest subsegment with l as the left endpoint in [l, r]
RSum represents the sum of the largest subsegment with r as the right endpoint in [l, r]
MSum represents the sum of the largest subsegment in [l, r]
ISum represents the sum of the interval of [l, r]
Hereinafter, [l, m] is the “left subinterval” of [l, r], and [m + 1, r] is the “right subinterval” of [l, r]. We consider how to maintain these quantities (how to combine the information of [l, r] through the information of the left and right subintervals)? For the interval [i, i] of length 1, the values of the four quantities are equal to $a_i $. For intervals of length greater than 1:

The first thing that is best maintained is the iSum. The iSum of the interval [l, r] is equal to the iSum of the “left subinterval” plus the iSum of the “right subinterval”.
For the lSum of [l, r], there are two possibilities, it is either equal to the lSum of the “left subinterval”, or equal to the iSum of the “left subinterval” plus the lSum of the “right subinterval”, whichever is greater.
For the rSum of [l, r], in the same way, it is either equal to the rSum of the “right subinterval”, or equal to the iSum of the “right subinterval” plus the rSum of the “left subinterval”, whichever is greater.
After calculating the above three quantities, it is easy to calculate the mSum of [l, r]. We can consider whether the interval corresponding to the mSum of [l, r] spans m - it may not span m, that is, the mSum of [l, r] may be one of the mSum of the “left subinterval” and the mSum of the “right subinterval”; it may also span m, it may be the sum of the rSum of the “left subinterval” and the lSum of the “right subinterval”. The greater of the three.
This way the problem is solved.

class status {
    constructor (lSum, rSum, mSum, iSum) {
        this.lSum = lSum;
        this.rSum = rSum;
        this.mSum = mSum;
        this.iSum = iSum;
    }
}

const pushUp = (l, r) => {
    const iSum = l.iSum + r.iSum;
    const lSum = Math.max(l.iSum + r.lSum, l.lSum);
    const rSum = Math.max(r.iSum + l.rSum, r.rSum);
    const mSum = Math.max(l.mSum, r.mSum, l.rSum + r.lSum);
    return new status(lSum, rSum, mSum, iSum);
}

const get = (nums, l, r) => {
    if (l = r) {
        return new status(nums[l], nums[l], nums[l], nums[l]);
    }
    const m = Math.floor((l + r) / 2);
    const lsub = get(nums, l, m);
    const rsub = get(nums, m + 1, r);
    return pushUp(lsub, rsub);
}

var maxSubArray = function(nums) {
    return get(nums, 0, nums.length - 1).mSum;
};

Kinematic solution

var maxSubArray = function(nums) {
    let pre = 0, max = nums[0];
    for (let i = 0; i < nums.length; i++) {
        pre = Math.max(pre + nums[i], nums[i]);
        max = Math.max(pre, max)
    }
    return max;
};

Reference article:

https://zhuanlan.zhihu.com/p/45986027