Data Structures and Algorithms | Part One Lesson Two: Little Ducks Travel

Posted May 27, 20205 min read

Program = data structure + algorithm

Author Xie Enming, the public number " Programmer Union ".
Reprint please indicate the source.
Original: https://www.jianshu.com/p/31d...


"Data Structure and Algorithm" full series

brief introduction


  1. Lead the story of algorithm complexity
  2. Two algorithms
  3. Comparison of the two algorithms
  4. The first part of the third lesson

1 . Lead to the story of algorithm complexity


In the previous lesson Data Structures and Algorithms | Part I, Lesson 1:What are Data Structures and Algorithms , we had a preliminary understanding of data structures and algorithms.

Since we are going to start learning algorithms, we cannot but mention the complexity of the algorithm.

But before we start talking about the complexity of the algorithm(Complexity), I hope to tell you a short story.

This easy little story can help you better understand the algorithm complexity later.

The reason why today s story is titled "Little Ducks Go Traveling" is because I watched the second season of "Longing for Life" before. Teacher He has a sheepfold on the edge of their house. Sheep, there is a chicken coop next to the sheepfold, and a nest of ducklings was raised later.

On several occasions, this nest of ducklings sneaked out of the henhouse from the cracks and ran to the small pool in the field near the house to swim. So I thought of using ducklings as examples.

Little Ducks


Our story is this:

Farmer Oscar is a very friendly farmer. He raises a lot of little ducks(I know you might imagine how they grow up and the Beijing roast duck ... Well, hurry up and stop this "evil" idea) .

The farmer Osacr has a good relationship with these ducklings. They can usually go out to wander around and enjoy a heated hut in winter. But what really excites these ducklings is:Oscar will drive a truck in the hottest summer each year, carrying the ducklings to the foot of the mountain farther away from home for vacation. There are many small ponds. Ducklings can spend time in the small pond foraging, playing, and playing.

Before leaving, farmer Oscar will first put a big box on his big truck, and then put the little ducks in the big box one by one. The big box is square and divided into one compartment, and each duckling lies in a small compartment. There are N compartments in length and width, where N is a number that we don't know yet. The number of ponds is also N.

But here comes the problem:when on vacation, the ducklings have requirements, and each duckling tells Oscar that they want to stay away from the hustle and bustle and try to go to a cleaner pond(with fewer ducks).

2 . Two algorithms


Every year in the past, farmer Oscar did n t want to bother, so he did this:

After arriving at the destination, Oscar parked the truck near the pond(the number of ponds is N), got off the truck, opened the rear door, took one from the box of ducks, and asked it:"You want Which pond do you go to? ". Once the duckling selected a pond, Oscar ran to the pond and put the duckling in.

After the first duckling was placed in the pond he wanted to go to, Oscar ran back to the truck and then asked the second duckling which pond he wanted to choose.

Because a duckling has chosen one of the ponds, since these ducklings want to go to a pond with less ducks and cleaner, so the second duckling will definitely choose a pond where there are no ducklings in it, then Oscar is another Trot.

Oscar went on to ask a little duck in this way, and put each little duck in the pond they wanted to go to.

N ponds have gradually begun to be occupied by ducklings. Once there are fewer ducks in the pond than in other ponds, then the little duck will choose this pond. Obviously, after the ducklings enter, the number of ducks in this pond will increase.

As you can imagine, after Oscar finally put all the ducklings in the pond they wanted to go to, the scenario should be:N ponds, each with the same number of N ducklings.

This year, the farmer Oscar is a little tired of having to go back and forth between the truck and the pond every time, just to put a little duck, which takes too much time and energy.

He thought of a good idea:every time, he would pick up N ducklings, go to an empty pond, and put the N ducklings inside. Then he returned to the truck and put another batch of N ducklings in an empty pond.

In this way, he only needs to return to the truck N times, and he can put all the ducks. And the situation at the end is the same as in previous years:N ponds, each with the same number of N ducklings.

Because the final distribution result is the same as in previous years, the ducklings have no complaints.

3 . Comparison of the two algorithms


Farmer Oscar s method of placing ducklings in a pond can be called an algorithm . Because this algorithm is an accurate description of the problem of "place a duck".

The algorithm of previous years and the new algorithm of this year, they both meet the final condition:after the placement, there are no more or less ducklings in any pond, and there are N ducklings in each pond.

Therefore, the algorithm of previous years and the algorithm of this year have met the requirements of the ducklings, and are all qualified algorithms.

The difference between the two algorithms is that in the first algorithm in previous years, each duckling asked Oscar to put it in a different pond, so Oscar needs to travel between the truck and the pond and the number of ducklings is The same is N x N, which is the square of N. And this year's second algorithm, Oscar only needs N round trips.

There is no doubt that this year's new algorithm is more efficient, and the time saved is proportional to the number of ducks.

Assuming N is 6, then the big box has 6 rows and 6 columns, and the number of ducks is 36. If the average time for Oscar to travel back and forth between the truck and the pond is 5 minutes, then the second algorithm only needs 6 x 5 = 30 minutes. The first algorithm requires 6 x 6 x 5 = 180 minutes, which is three hours, which is 6 times that of the second algorithm.

The difference between the two algorithms will continue to expand as the number of ducks increases:assuming N is 24, then the big box has 24 rows and 24 columns, and there are 576 ducks. If the average time for Oscar to travel back and forth between the truck and the pond is still 5 minutes, then the second algorithm only needs 24 x 5 = 120 minutes, which is 2 hours. The first algorithm takes 24 x 24 x 5 = 2880 minutes, which is 48 hours, which is 24 times that of the second algorithm.

Obviously farmer Oscar's new algorithm is much better. In computer terminology, we would say that his new algorithm is more efficient and has higher performance. We can use "complexity"(Complexity) to quantify this performance, we will learn the complexity of the algorithm in the next lesson.

4 . The first part of the third lesson


Today's class is here, come on!

Next lesson: Data Structure and Algorithms | Part Three Lesson 3:Algorithm Complexity


My name is , the public number "[Programmer League]( https://github.com/frogoscar/ProgrammerLeague/blob/master/qrcode . "jpg)" operator, elite lecturer Ms. Oscar , a lifelong learner.
Love life, like swimming and have a little understanding of cooking.
Life motto:"Go straight to the benchmark"