Column website www.jiuzhang.com | | nine chapters algorithm

Many students ask me:

Why are greedy algorithms not included in the course, and can they be included in the lesson plan?Copy the code

Every time I always tried to persuade them:

Don't waste your time on covetousness. It's useless.Copy the code

Why is learning the greedy method useless?

This is a question worthy of discussion. From my point of view, there are three reasons as follows:

1. All the greedy methods you want are wrong.

First of all, we need to know what the greedy method is. The greedy method is like choosing a husband based only on whether he is rich at present, not whether he will be successful in the future. Some other algorithms, such as dynamic programming, are just like you find through careful investigation that although he is now a poor boy, he is unwilling to accept his father’s arrangement and go out on his own because he is a rich second generation, but he will eventually inherit billions of dollars in the future.

Thus, the greedy method is, so to speak, a “short-sighted” algorithm. Generally in the algorithm problem, can use greedy algorithm problem, its greedy strategy is often more complex, ordinary people is unexpected. And the greedy strategies you tend to think of are often wrong.

Take A practical example: Find the shortest path from point A to point B on the graph (the distance between points is A positive integer).

Wrong greedy strategy: Start from A, select the nearest point X in A, go to X, then select the nearest point Y, go to Y…

The right greedy strategy: Use hashm ap distance = {} to record the shortest distance from all points to the starting point A. We start with distance equals, which means that at the moment only A is the shortest distance from the starting point that we know for sure. Then find the smallest pair of X and Y between points in Distance and points in non-distance to minimize Distance [X]+ (direct connection Distance from X to Y). Where X is in distance (which has been confirmed to have found the shortest distance) and Y is not in distance (which has not been confirmed to have found the shortest distance). Then add Y to distance and set the distance to distance[X]+ (the direct connection distance from X to Y).

Well, isn’t the right greedy algorithm very complicated?

2. Interviews are almost impossible

Greedy method of the problem, the interview will not take an examination of the basic, because the same as taking an examination of intelligence or recitation. It’s very difficult for an interviewer to create an interview question out of thin air using a greedy algorithm. (See LintCode for the percentage of greedy algorithms.) In this case, if you are asked about greedy algorithms in an interview, it must be a classic greedy question, which we can call a recitation question. Because most students (with the exception of those with high IQs or algorithmic competition experience) will not be able to come up with solutions in an interview.

For example: Gas Station www.lintcode.com /en/problem… The way to do this problem is to start at any station, walk around, find the station with the least amount of G as left in the circle, and then walk around from this station. If you can finish the whole journey from this station, you can do it, otherwise you can’t. An algorithm like this requires mathematical proof to prove its correctness, and the interviewer is not capable of such interview questions.

From another point of view, greedy algorithm questions, for the implementation of the program is not high requirements, but also in violation of the company through the algorithm questions interview is mainly hope to examine everyone’s program implementation ability this point. So neither interviewers nor companies tend to use greedy algorithms as an algorithmic problem for interviews.

3. No generality

Dichotomy, dynamic programming algorithm, divide-and-conquer algorithm, search algorithm and so on, many algorithms are universal. In other words, in problem A, you used this algorithm, and in other problem B, you could probably use exactly the same algorithm and idea.

And greedy law, he is not “an algorithm”, but “a class of algorithms” collectively. So basically what happens is, you solve this problem with some greedy algorithm in problem A, and then the greedy algorithm used in this problem, you’ll never find A second problem that can be solved in A similar way.

Each question is completely independent and has no connection, which is nothing more than the more the learner recites, the more he knows. No analogy, no analogy. Therefore, wasting time on avarice is thankless.

Of course, the interview is not to say that it is completely impossible to encounter greedy algorithms, but the odds are very small, as long as you recite a few classic topics.



Welcome to follow my wechat official account: Ninechapter.



Elite programmer exchange community, regular release of interview questions, interview skills, job information, etc

Nine chapters algorithm, IT education field of deep cultivator