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

This article mainly explains "how to manage the recursive algorithm of c language". The content of the explanation in this article is simple and clear, and it is easy to learn and understand. let's study and learn how to manage the recursive algorithm of c language.

Algorithm idea

As we all know, a method that calls itself is recursive, yes, but this is only the most superficial understanding of recursion.

So what is the essence of recursion?

A: the essence of recursion is to decompose a big problem into smaller ones, and then when we get the solution of the small problem, we can use the solution of the small problem to construct the solution of the big problem.

How did you get the solution to that little problem?

A: it is constructed from the solution of a smaller problem, and when it is too small to be too small, it is the time of the zero problem, that is, base case.

So summarize the three steps of recursion:

Base case: it is the zero number problem of recursion, and it is also the end point of recursion. If you go to the smallest problem, you can give the result directly, and you don't have to go any further, otherwise, it will become an endless cycle.

Disassemble: the problem of each layer has to be smaller than that of the previous layer, and the size of the problem is constantly shrinking in order to go from big to small to base case.

Combination: get the solution of the small problem, but also know how to construct the solution of the big problem.

So each recursive question, we follow these three steps to analyze, figure out these three problems, the code is very easy to write.

Fibonacci series

Although this question is a clich é, I believe what I share here will give you something else.

Topic description

Fibonacci series is an Italian mathematician who has nothing to do to study the process of rabbit breeding. After studying it, he found that it can be written into such a sequence: 1, 1, 1, 2, 3, 3, 5, 8, 13, 21. That is, each number is equal to the sum of its first two numbers. So I'll give you the nth number and ask what F (n) is.

Analysis

It is very simple to express it in mathematical formula:

The code is also simple, with the three steps we just summarized:

Base case: F (0) = 0, f (1) = 1.

Decompose: F (nMel 1), f (nMel 2)

Combination: F (n) = f (nmur1) + f (nmur2)

Then write it as follows:

Class Solution {public int fib (int N) {if (N = = 0) {return 0;} else if (N = = 1) {return 1;} return fib (Nmer 1) + fib (N = 2);}}

But the speed experience of this solution given by Leetcode is only faster than the 15% answer, because its time complexity is too high!

Process analysis

So this is the first point I want to share, how to analyze the process of recursion.

First of all, we draw this Recursion Tree, for example, we draw the recursive tree of F (5):

What is the actual implementation route?

The first is to follow the leftmost line all the way to the end: F (5) → F (4) → F (3) → F (2) → F (1). Finally, there is a base case that can return to F (1) = 1, then go back to the layer of F (2), and then go down to F (0), hit the bottom, bounce back to F (2), get the result of F (2) = 1, 0 = 1, and return the result to F (3). Then go to F (1), get the result and return to F (3) to get F (3) = left + right = 2, and then go back to the result.

This method is essentially created by the von Neumann system of our computer. at present, a CPU core can only execute one instruction at a time, so F (3) and F (4) cannot be carried out together. F (4) must be executed first (this code puts fib (NMUE 1) in front of it), and then F (3).

We can see what's going on inside the stack in debug in IDE: this is indeed the leftmost line that goes first, with a total of five layers, and then back up layer by layer.

Time complexity analysis

How to evaluate the quality of an algorithm?

There are many solutions to many problems. After all, all roads lead to Rome. But how to evaluate the advantages and disadvantages of each method, we usually use the large O expression to measure the time and space complexity.

Time complexity: the increase of the time required by the algorithm with the increase of the independent variable.

Here big O represents the performance of an algorithm in worst case, this is what we are most concerned about, otherwise the Spring Festival travel system hold will not live, you told me that this algorithm is very good?

Of course, there are other ways to measure time and space, such as

Theta: describes tight bound

Omega (n): this describes best case. At best, it doesn't make any sense.

It also gives us some inspiration, not to say how good your performance is, it doesn't make sense; the interview measures your level in worst case; don't say that the interview didn't give full play to your true level, what is gripping is that that is our true level.

What is the time complexity for this problem?

A: because we have walked through each node, the time of all the nodes is the total time.

Here, what we do on each node is the sum, which is the operation of O (1), and the time of each node is the same, so:

Total time = number of nodes * time per node

It becomes a mathematical problem of finding the number of nodes:

At N = 5

There is one node on the top floor.

Two on the second floor

Four on the third floor

Eight on the fourth floor

Sixteen on the fifth floor, if full, imagine a big tree:)

Don't worry about this unfilled place here, there must be such a few node, but the time complexity of Big O expression we just talked about, we are asking for worst case.

Then the total number of nodes is:

1 + 2 + 4 + 8 + 16

This is the sum of a proportional series, and of course you can use a mathematical formula to calculate it, but there is a little trick that can help you calculate quickly:

In fact, the total number of nodes in each layer will not exceed the number of nodes in the last layer, and the total number of nodes is at most the number of nodes in the last layer * 2, and then the constant term does not matter in the time complexity of big O, so the total time complexity is:

Number of nodes in the last layer: 2 ^ n

Don't you get it? Don't panic, go to bilibili / YouTube to see my video explanation, just search "Tian Xiaoqi".

Space complexity analysis

In general, the space complexity written in books refers to:

All the memory space required during the operation of the algorithm

But what is commonly used in the company, which is also asked during the interview is

Auxiliary space complexity:

The additional space required to run the algorithm.

Give an example to illustrate the difference: for example, if the result asks you to output an array of length n, then the O (n) space is not included in the space complexity of the algorithm, because this space cannot escape and does not depend on your algorithm.

How to analyze the space complexity?

We just talked about the von Neumann system, and it is easy to see from the figure that the leftmost route takes up the most space in stack and keeps pressing the stack, that is, from 5 to 4 to 3 to 2 to 1 until base case returns. The space complexity of each node is O (1), so the total space complexity is O (n).

I'm up there? It is also mentioned in the video that students who do not understand look up at the video.

Optimization algorithm

Then we think, why does such a simple operation require exponential time complexity? Why on earth makes time so big.

It's not hard to see that there's too much double counting in this Recursion Tree.

For example, an F (2) has been calculated three times here, and F (3) has been calculated twice, and each time it has to be recalculated. Isn't this a bear breaking a stick? it's really a bitter tear.

After finding out the reason, in order to solve this kind of double calculation, computers actually use the same method as we humans: take notes.

For many professions, such as doctors, lawyers, and our engineers, why is the older experience valuable? Because we see more and accumulate more, the next time we encounter a similar problem, we can quickly give a solution, even if it can not be solved for a while, but also avoid some blind trial and error, we will stand at the height of the past and make continuous progress. Instead of starting from scratch every time.

Coming back to the optimization algorithm, how does the computer take notes?

If we want to get F (n), we just want to

Record the value of F (0) ~ F (nmur1)

Then just choose an appropriate data structure to store.

So it's obvious here that you can use the HashMap mentioned before or use an array to save it:

Index012345F (n) 011235

With this cheat sheet, we can get the results from front to back, so that each point is only calculated once, and the code is very simple with a for loop.

Class Solution {public int fib (int N) {if (n = 0) {return 0;} if (n = 1) {return 1;} int [] notes = new int [n = 1]; notes [0] = 0; notes [1] = 1; for (int I = 2; I

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.