Shulou(Shulou.com)06/03 Report--

This article mainly introduces "what is the branching algorithm". In the daily operation, I believe that many people have doubts about what the branching algorithm is. The editor consulted all kinds of data and sorted out the simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubts about "what is a branching algorithm"! Next, please follow the editor to study!

Preface

Divide-and-conquer algorithm (divide and conquer) is one of the five commonly used algorithms (divide-and-conquer algorithm, dynamic programming algorithm, greedy algorithm, backtracking method, divide-and-conquer boundary method). Many people may only know the divide-and-conquer algorithm, but there may be no systematic learning divide-and-conquer algorithm. This article will take you to understand and understand the divide-and-conquer algorithm in a more comprehensive way.

Before learning the divide and conquer algorithm, let me ask you a question. I believe we all had the experience of piggy bank when we were young. If parents and relatives give money, they will save money in their own treasure, and we will count the money every once in a while. But a pile of money for you to deal with, you may feel very complicated, because the data is a little large relative to the brain, and it is easy to miscalculate, you may divide it into several small parts, and then add it up to calculate the total amount of the pile of money.

Of course, if you think the amount of money in each part is still too large, you can still divide it and merge it. The reason why we have so much money is because:

The way to calculate each small pile of money is the same as the way to calculate the maximum pile (the difference lies in volume)

Then the sum of a lot of money is actually the sum of a small pile of money. In this way, there is actually a kind of thought of partition and rule.

Of course, the money was all come up with.

Introduction of divide-and-conquer algorithm

Divide-and-conquer algorithm is an algorithm that uses the idea of divide-and-conquer. What is divide-and-conquer?

Divide and conquer, literally "divide and conquer", that is, divide a complex problem into two or more identical or similar sub-problems, and then divide the sub-problems into smaller sub-problems. Until finally, the sub-problem can be solved simply and directly, and the solution of the original problem is the combination of the solutions of the sub-problem. In computer science, divide-and-conquer is a very important algorithm using the idea of divide and conquer. Divide-and-conquer method is the basis of many efficient algorithms, such as sorting algorithm (fast sorting, merge sorting), Fourier transform (fast Fourier transform) and so on.

The parent problem is decomposed into child problems to be solved in the same way, which is consistent with the concept of recursion, so divide-and-conquer algorithms are usually implemented recursively (of course, there are also non-recursive implementations). The description of the divide-and-conquer algorithm is also easy to understand literally, but there is actually a process of merging:

Divide: recursively solve smaller problems (stop at the termination layer or when it can be solved)

Conquer: recursive solution, if the problem is small enough to solve directly.

Combine: construct a parent problem from the solution of a child problem

The general divide-and-conquer algorithm is decomposed into two or more recursive calls in the text, and the subclass problems generally do not intersect (do not affect each other). When the scale of solving a problem is very large and difficult to solve directly, but when the scale is small, the problem is easy to solve and the problem meets the applicable conditions of the divide-and-conquer algorithm, then the divide-and-conquer algorithm can be used.

So what conditions (characteristics) do the problems solved by divide-and-conquer algorithm need to meet?

1. The scale of the original problem is usually large and not easy to be solved directly, but the problem can be solved more easily when it is reduced to a certain extent.

2. The problem can be decomposed into several sub-problems with small scale and the same (similar) solution. And the solution of the sub-problems is independent and independent of each other.

3. The solution of the problem can be obtained by combining the sub-problems of the decomposition of the problem.

You may wonder what the divide-and-conquer algorithm has to do with recursion. In fact, the important thing of partition and rule is a kind of thought, which pays attention to the process of dividing, managing and merging problems. Recursion is a way (tool), which forms a back-and-forth process by calling the method itself, and divide and conquer may take advantage of such a process back and forth many times.

Classical problems of divide-and-conquer algorithm

For the classic problem of divide-and-conquer algorithm, the important thing is its idea, because most of us use recursion to implement, so most of the code implementation is very simple, and this article also focuses on the idea.

The classical problem of divide-and-conquer algorithm is divided into two categories: the sub-problem is completely independent and the sub-problem is not completely independent.

1. The complete independence of the subproblem means that the answer to the original question can be derived entirely from the result of the subproblem.

2. The subproblems are not completely independent, and some interval problems or cross-interval problems may result in cross-interval problems, which need to be carefully used for reference when considering the problem.

Binary search

Binary search is an example of divide and conquer, but binary search has its own particularity.

Sequence order

The result is a value

The normal dichotomy divides a complete interval into two intervals, which should find the value separately and then confirm the result, but the ordered interval can directly determine which interval the result is in, so the two intervals only need to calculate one of the intervals, and then continue until the end. There are recursive and non-recursive implementations, but non-recursion is more common:

Public int searchInsert (int [] nums, int target) {if (nums [0] > = target) return 0 if / pruning if (nums [nums.length-1] = = target) return nums.length-1;// pruning if (nums [nums.length-1] high) / / as a cut-off condition return; int [low]; / / extra space k, take the leftmost one as a measure, and finally require that the left side is smaller than it and the right side is larger than it. While (low

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.