/ Data Structure and Algorithms  

Divide-and-conquer Algorithm

Basic Concept

In computer science, divide-and-conquer is an important algorithm. The literal explanation is “divide and conquer”, which is to divide a complex problem into two or more identical or similar subproblems, and then divide the subproblems into smaller subproblems, until the final subproblem can be directly solved. The solution of the original problem is the combination of the solutions of the subproblems. This technique is the basis of many efficient algorithms, such as sorting algorithms (quick sort, merge sort), Fourier transform(fast Fourier transform), etc.

The computational time required for any problem that can be solved by a computer depends on its size. The smaller the scale of the problem, the easier it can be solved directly, and the less calculation time required to solve the problem. For example, for the ordering problem of n elements, when n = 1, no calculation is needed. When n = 2, only one comparison is needed 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. Sometimes it is quite difficult to directly solve a large-scale problem.

Basic ideas and strategies

The idea of the divide-and-conquer method is to divide a large problem that is difficult to solve directly into some smaller and identical problems, so that each one can be solved.

The divide-and-conquer strategy is: for a problem of size n, if the problem can be easily solved (for example, the size of n is small), solve it directly, otherwise it is decomposed into k small-scale sub-problems, which are mutually independently and in the same form as the original problem, solve these sub-problems recursively, and then combine the solutions of the sub-problems 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 are solvable, and the solutions of these sub-problems can be used to obtain the solution of the original problem, then this divide-and-conquer method is feasible. The subproblems generated by the divide-and-conquer method are often smaller models of the original problem, which facilitates the use of recursive techniques. In this case, repeated application of divide-and-conquer means we can make the sub-problem consistent with the original problem but its size is constantly shrinking, and eventually the sub-problem is reduced to a very easy solution. This naturally leads to a recursive process. Divide-and-conquer and recursion are like twin brothers, which are often applied in algorithm design at the same time, and many efficient algorithms are generated from it.

Scope of application

The problems that can be solved by the divide-and-conquer method generally have the following characteristics:

  • The problem can be easily solved by reducing the scale to a certain extent;
  • The problem can be decomposed into several smaller and identical problems, that is, the problem has the optimal substructure property;
  • The solutions of the sub-problems decomposed by the problem can be combined into the solution of the problem;
  • The sub-problems decomposed by this problem are independent, that is, there is no common sub-sub-problem among the sub-problems.

Most problems satisfy the first characteristic, because the computational complexity of the problem generally increases as the problem size increases;

The second characteristic is the premise of applying the divide-and-conquer method. It is also sufficient for most problems. This feature reflects the application of recursive thinking.

The third feature is the key. Whether the divide-and-conquer method can be used depends entirely on whether the problem has the third feature. If the first and second features are available, and the third feature is not available, then the greedy or dynamic programming can be considered..

The fourth characteristic relates to the efficiency of the divide-and-conquer method. If the sub-problems are not independent, the divide-and-conquer method has to do a lot of unnecessary work and repeatedly solve common sub-problems. Although the divide-and-conquer method is available at this time, the dynamic programming method is generally better.

Steps to solve problems using divide-and-conquer

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

  1. Decomposition: Decompose the original problem into several smaller, independent sub-problems in the same form as the original problem;
  2. Solution: If the sub-problem is small and can be easily solved, then directly solve it, otherwise recursively solve each sub-problem
  3. Merge: Combine the solutions of each sub-problem into the solution of the original problem.

Its general algorithm design pattern is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

        // Recursively solve Pi
        5. do yi ← Divide-and-Conquer (Pi)

    // Merge solutions
    6. T ← MERGE (y1, y2, ..., yk)

    7. return (T)

|P| represents the scale of the problem P; n0 is a threshold value, which means that when the scale of the problem P does not exceed n0, the problem is easily solved directly, and it is not necessary to continue to decompose. ADHOC(P) is the basic sub-algorithm in this divide-and-conquer method, which is used to directly solve small-scale problems P. Therefore, when the scale of P does not exceed n0, it is directly solved by the algorithm ADHOC(P). The algorithm MERGE(y1, y2, ..., yk) is a merged sub-algorithm in this divide-and-conquer method, which is used to merge the corresponding solutions y1, y2, … of P‘s subproblems P1, P2, …, Pk ., yk for probblem P.

Complexity analysis of divide-and-conquer

A divide-and-conquer method divides a problem of size n into k sub-problems of size n/m to solve. It is assumed that the decomposition threshold n0 = 1 and the adhoc solution scale of 1 take 1 unit time. It is further assumed that f(n) unit time is required to decompose the original problem into k sub-problems and merge the solutions of the k sub-problems into solutions of the original problem. Using T(n) to represent the calculation time required for this divide-and-conquer method to solve a problem of scale |P| = n, then:

1
T(n）= k*T(n/m)+f(n)

Find the solution to the equation by iteration:

The recursive equation and its solution only give the value of T(n) when n is equal to the power of m, but if T(n) is considered smooth enough, then T(n)‘s growth rate can be estimated by the value of T(n) when n is equal to the power of m. It is generally assumed that T(n) rises monotonically, so that when mi <= n < mi + 1, T(mi) ≤ T(n) < T(mi + 1).

Some classic problems that can be solved using divide-and-conquer

  1. Binary search
  2. Large integer multiplication
  3. Strassen matrix multiplication
  4. Checkerboard coverage
  5. Merge and sort
  6. Quick sort
  7. Linear time selection
  8. Closest point pair problem
  9. Round robin schedule
  10. Hanoi Tower

Thinking process when designing procedures based on divide-and-conquer

In fact, it is similar to the mathematical induction method, find the solution equation formula to solve this problem, and then design the recursive program according to the equation formula.

  1. Must found the solution for the minimum problem size
  2. Then consider the solution as the problem size increases
  3. After finding the recursive function to solve (various scales or factors), design the recursive program.