This is the 15th day of my participation in Gwen Challenge

A brief introduction to the idea of divide and conquer

Divide and conquer: Divide and conquer. Divide a big problem that is difficult to be solved directly into some smaller sub-problems, so that they can be defeated separately and divided and ruled.

So if you incorporate divide-and-conquer into an algorithm, the most typical data structure is an array, where you split an array out of order down the middle, and then split it again, until it’s as small as it can be that it has length one. Then it’s easier to do it on an array of length 1 than it is to do it directly.

This thought, our ancestor summed up another sentence: big things become small, small things become small.

But not all the data in the array structure can be used, depending on whether the following conditions are met:

  1. The problem can be easily solved if it is scaled down to a certain extent

  2. The problem can be decomposed into several similar problems of smaller scale, that is, the problem has the property of optimal substructure.

  3. The solutions of subproblems decomposed by this problem can be combined into the solutions of this problem.

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

A classic case

Here to sort algorithm merge (merge) algorithm, quick sort algorithm for example. We also discuss the application of these two algorithms to the divide-and-conquer idea.

Tips: Understand the logic of the algorithm itself before you understand the business logic; To clarify the logic of the algorithm, we need to make clear what his core idea is first.

Merge sort

Merge sort, you split the array in the middle, and then you split it all the way down, until you have only one particle left, and then you merge sort.

As shown in the figure below, the upper part is about the process of data splitting. , divided into the smallest particles; The bottom half is merged and sorted.

The code implementation is as follows:

/ * * *@param {Array} Arr The sorted Array * return {Array} the sorted Array */
function mergeSort(arr){
    let len - arr.length,
        middle = Math.floor(len / 2),
        left = [], right = [];
    If the length is less than 2, it contains 0 or 1 bits. In real services, you need to consider whether the type and value can be sorted.
    if(len < 2) return arr;
    // Split the array into left and right halves.
    left = arr.slice(0, middle);
    right = arr.slice(middle);
    
    return merge(left, right)
}
/ * * *@param {Array} Left The split left array *@param {Array} Return result Array of merged results */
function merge(left, right){
    const result = [];
    while(left.length && right.length){
        if(left[0] <= right[0]) result.push(left.shift())
        else result.push(right.shift())
    }
    
    while(left.length) result.push(left.shift())
    while(right.length) result.push(right.shift())
    
    return result;
}

mergeSort([1.5.6.2.4.3]) / / [6]
Copy the code

Advantage:

1, fast speed: time complexity O(nlogn)

2. Stability: if you encounter an array like [3,2,1,2], the order of the 2’s after sorting will not change, which is important in certain scenarios

Disadvantage:

The space complexity required is relatively high

Quick sort

Quicksort is also divide-and-conquer at its core, so it also splits and merges arrays in its implementation.

But unlike merge sort, quicksort determines a base value, and then compares it to the base value, less than to the left, more than to the right.

/ * * *@param {Array} Arr The Array to be sorted * return {Array} The result Array to be sorted */
function quickSort(arr){
    if(arr.length <= 1) return arr;
    
    let len = arr.length,
        left = [], right = [];
    
    const middleVar = arr.splice(Math.floor(len / 2), 1) [0];
    
    for(let i = 0; i < arr.length; i++){
        if(arr[i] < middleVar) left.push(arr[i]);
        else right.push(arr[i]);
    }
    
    return quickSort(left).concat(middleVar, quickSort(right));
}
Copy the code

Advantage:

1, fast speed: time complexity O(nlogn)

Disadvantage:

1. Relatively high space complexity is required

2, unstable, because each comparison, may not be adjacent, may break the order of the same value.

conclusion

The idea of divide and conquer and its cases are written here, but in algorithm learning, the application of the idea of divide and conquer is not limited to this, but also such as binary search, checkerboard covering problem.

But the idea of divide and conquer is the core idea, the foundation, the most important idea of this kind of problem. It requires priority, in-depth study and mastery.

Modao does not mistakenly cut wood work, can master, analyze the core ideas, and the corresponding algorithm learning, and finally combined with business needs for practical use will come naturally.

Make a little progress every day.