preface
This is the classic algorithm idea, divide-and-conquer, you can call it an idea, you can call it a divide-and-conquer algorithm, but just to distinguish it, we’re going to call it divide-and-conquer.
If you don’t know what divide-and-conquer is, or know something about it, but know exactly how it works backwards, then this article might be for you to read.
❝
My understanding of the divide-and-conquer algorithm:
Its basic idea is to decompose a problem of size N into K smaller sub-problems, which are independent of each other and have the same nature as the original problem.
The solution of the original problem can be obtained by solving the sub-problem, which can be understood as an algorithm of subobjective completion program.
Dichotomy is a divide-and-conquer idea a lot of the time.
❞
Then around the following points to introduce the divide-and-conquer algorithm 👇
- The basic idea
- Application and which classical problems to solve
- The classic example
Contact 👉TianTianUp. If you have any questions, you can contact the author.
Basic thought of divide-and-conquer
In a word, divide and conquer sums it up 👇
The original problem is divided into N sub-problems with small scale and similar structure to the original problem. These sub-problems are solved recursively, and then the results are combined successively. Finally, the solution of the original problem is obtained.
So specifically, it seems that we can divide it into three steps 👇
- Decomposition: The problem to be solved is divided into several similar problems of smaller scale.
- Solution: When subproblems are small enough, solve them in simpler ways.
- Merge: according to the requirements of the original problem, the solution of the sub-problem is merged layer by layer to form the solution of the original problem.
In fact, the idea is still the same, a big problem that is difficult to solve directly, divided into a number of small scale of the same problem, in order to defeat each, divide and rule.
Application of divide-and-conquer
Using divide-and-conquer to solve a problem depends on whether we can grasp several characteristics of divide-and-conquer:
- A problem can be reduced to a point, to a smaller problem to solve.
- If you break it down into smaller problems, smaller problems of the same kind, then the problem should be the optimal substructure.
- The solution of subproblem decomposed by this problem is combined into the solution of this problem.
- Each subproblem decomposed is independent of each other, that is, there is no common subproblem among the subproblems.
Let’s talk about these characteristics
❝
The first characteristic: The computational complexity of a problem generally increases with the size of the problem, so most problems are satisfied.
The second characteristic is that divide-and-conquer is applied only if it is satisfied, and you can think of it as somehow reflecting the application of the recursive idea.
The third characteristic: this should be the key of divide-and-conquer method, can use divide-and-conquer method completely depends on whether the problem has the third characteristic, if has the first and second characteristic, but does not have the third characteristic, can consider using greedy method or dynamic programming method.
The fourth feature relates to the efficiency of divide-and-conquer method. If each subproblem is not independent, divide-and-conquer method needs to do a lot of unnecessary work and repeatedly solve common subproblems. At this time, although divide-and-conquer method can be used, dynamic programming method is generally better.
❞
To understand the characteristics of divide-and-conquer, let’s take a look at some classic problems that use this idea to solve problems 👇
Divide and conquer to solve classical problems
Under what circumstances, can use this idea to solve it, the following content collected from the Internet 👇
(1) Binary search
(2) Multiplication of large integers
(3) Strassen matrix multiplication
(4) checkerboard coverage
(5) merge sort
(6) Quicksort
(7) Linear time selection
(8) The closest point-pair problem
(9) Round robin schedule
(10) Hannott Tower
What I want to mention is merge sort, which implements the idea of divide-and-conquer, breaking up big problems, solving small problems, and finally merging. So let’s look at the merge sort code 👇
And the idea of merge sort, how it works, and we talked about it in the sorting chapter, is divide-and-conquer, so you can see how it works, but I’m not going to go into that.
Two examples
Next, let’s take three problems as examples to see how the idea of divide and conquer can be used to solve problems 👇
Maximum suborder and ⭐
❝
Link: maximum suborder sum
❞
Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.
Example:
❝
Input: [-2,1,-3,4,-1,2,1,-5,4] output: 6
Explanation: The maximum sum of continuous subarrays [4,-1,2,1] is 6.
❞
❝
Advanced:
If you already have an O(n) solution, try a more sophisticated divide-and-conquer solution.
❞
Source: LeetCode Link: https://leetcode-cn.com/problems/maximum-subarray Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
First of all, let’s see if we can solve this problem in order n, but if we think about it, we can do it in a simple way
More importantly, let’s try to solve this problem divide-and-conquer. For the maximum suborder sum of an array, its contribution to the answer can only be 👇
- It’s on the left side
- It’s on the right side
- In the middle, through the middle.
So can we recursively, for the answers that appear on the left and the answers that appear on the right, we can treat them as one case and then recurse, and of course the exit of the recursion, obviously, when the length of the recursion array is 1, we need to recurse.
In the case of the middle answer, we can calculate the answer, so the idea is clear, next, let’s see how to write 👇
Of course, this problem is better solved with dynamic programming ideas, but also better to understand 👇
❝
//dp[I] represents the maximum sum of subsequences ending in nums[I]
❞
The code point here is ☑️
Search the two-dimensional matrix II⭐⭐
❝
Link: Search two-dimensional matrix II
❞
Write an efficient algorithm to search a target value in m x n matrix matrix. The matrix has the following properties:
The elements of each row are arranged in ascending order from left to right. The elements of each column are arranged from top to bottom. Example:
The existing matrix matrix is as follows:
❝
[[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]
❞
Given target = 5, return true.
Given target = 20, return false.
Source: LeetCode Link: https://leetcode-cn.com/problems/search-a-2d-matrix-ii Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
👉 Each row of the matrix is ascending from left to right, and each column is ascending from top to bottom. Find some number in the matrix.
Of course, we have a simple idea 👇
- Maintain two Pointers (row,col), and when the target element is found, we put back true
- When the value of the element pointing to the current is less than target, we move it up one line by col++.
- If the current value is greater than the current target, we row–, moving one column to the left.
- If we know the col > matrix row, or if row < 0, we return false to indicate that it does not exist.
Time complexity: O(n+m)
- The key to time complexity analysis is to note that at each iteration (we do not return true), rows or columns decrement/increment exactly once.
- Since rows can only be decreased m times and columns can only be increased N times, the while loop cannot run more than n+m times before causing it to terminate.
- Because all other work is constant, the total time complexity is linear in the sum of the matrix dimensions.
Based on the above pseudocode, we can basically solve the problem 👇
Such a solution is simple and easy to understand. In fact, this is not a real dichotomy, but a specific search method is used to complete the search of the matrix according to the particularity of data.
If we can reduce the complexity of a one-dimensional array to log time, can we do the same for a two-dimensional array?
This idea, can refer to 👇
- We can iterate through the diagonal of the matrix, search these rows and columns bisectively, slice them.
- Iterating over the diagonal, binary search for rows and columns until the diagonal iteration runs out (at which point you can return true or false)
And just to put it more simply, the idea of binary search is to look for rows and look for columns along a diagonal.
If you look at the code, you’ll see how to divide and conquer using the diagonal of a matrix.
The code point here is ☑️
Clear divide and conquer ideas, to its characteristics have a certain understanding, understand how to use it to solve practical problems, maybe this is the significance of this article ~
Topic summary
There are not many topics, but for a basic introduction to divide and conquer, it should be a good choice 👇
-
Maximum suborder sum
-
Continuous sequence
-
Segmentation array
❤️ thank you
If you find this article helpful:
- Click “like” to support it, so that more people can see this content.
- Pay attention to the public number “front-end UpUp”, contact the author 👉 “DayDay2021”, we learn together and progress.
- If you feel good, you can also read TianTian’s recent article (thanks to Digg friends for their encouragement and support 🌹🌹🌹) :
- “Algorithms and Data Structures” a brain map showing the beauty of dynamic programming algorithms (370+👍)
- Algorithms and Data Structures “The Beauty of DFS and BFS algorithms (240+👍)
- “Algorithms and Data Structures” sorting algorithms (220+👍)
- Algorithms and Data Structures takes you through the beauty of hashing algorithms (210+👍)
- “Algorithms and Data Structures” takes you through the beauty of backtracking algorithms (190+👍)
This article is formatted using MDNICE