When I first started programming, I didn't know anything about algorithms. Merge sort? Binary search? Quick sort? It wasn't fun at all to face any code around the algorithm, and I didn't understand it at all.
But when I heard the word algorithm, I had a scary impression. I had a strong impression that it was difficult and could only be used by really smart programmers. What is an algorithm?
That's true, and I felt the same way. But only recently have I been able to deal with algorithms.
Any algorithm is designed to solve some ** problem **. I want to extract only one target data from the data containing 10,000 random numbers. I want to prevent the data from being eavesdropped on the way Our world has a lot of problems
And in such a case, the algorithm is very useful.
In understanding any algorithm, let's pay attention to the ** 2 points ** that we will introduce. Then you will find that the world of algorithms is not as harsh as you might think.
An algorithm (English: algorithm [ˈælgəˌrɪðəm]) is a formalized representation of a procedure for solving a problem in mathematics, computing, linguistics, or related fields. Wikipedia
In other words, an algorithm is a procedure for solving a problem. In order to give a more detailed explanation, if we put out an algorithm that is familiar to us, ** Formula for finding the area of a circle ** This is also one of the finest algorithms
Speaking of a typical formula for finding the area of a circle,
Area of a circle = radius x radius x π
is not it. ** "I want to find the area of a circle quickly and as accurately as possible! When I run into the problem ** This algorithm was born in Greece long ago to solve this problem. This formula is a procedure for solving the problem of finding the area of a circle.
Isn't this a little lowering the threshold for the algorithm? To get a better understanding of the algorithm ■ ** What is the problem **, and ■ ** What is this algorithm solving? ** If you think about the above two points, your understanding will advance!
If the formula of the yen, I want to find the area of a circle quickly and as accurately as possible! The first problem was This algorithm can easily find the area of a circle as long as you include the radius of the circle.
Other algorithms can be thought of in the same way.
First of all, as a premise I have a problem An algorithm exists to solve it.
Let's do our best from here!
This time, I will focus on two types of algorithms and explain them in the following order. ■ Search algorithm ■ Sort algorithm
Of course, there are many other algorithms However, these two are typical algorithms that appear in the questions of university class exams and information technology engineer exams.
Also, if you search for algorithm, the sort algorithm will be hit first, To understand the sorting algorithm, you must first understand the search algorithm before you can understand what the sorting algorithm exists for. So first learn the search algorithm and then the sort algorithm
First, there is a search algorithm as an algorithm that you should remember. It sounds difficult at first glance, but it's very easy. An algorithm that finds the desired data from a huge data group It is called a search algorithm.
First, let's imagine with playing cards 13 heart-shaped playing cards are randomly arranged from 1 to K. At this time, what would you do if you were asked "Please answer where the 7 playing cards of the heart are"?
Perhaps many would flip through the cards one at a time looking for a hard 7 playing card. In the world of algorithms, this is called a linear search algorithm (or sequential search algorithm). It is called sequential search because it turns straight one by one. It is called a linear search because it does not skip one sheet in the middle or start turning from the middle, but continues the search from the beginning to the end until the desired data is found.
It's easy to replace this with a program Just turn it with a for statement
linear_search.py
# coding: utf-8
# Here your code !
def linear_search(card_list, card):
for i,element in enumerate(card_list):
if element == card:
print("{0}Second{1}There is".format(i+1,card))
return
print("{0}Was not".format(card))
return
if __name__ == '__main__':
heart_cards = ["h-5","h-J","h-2","h-9","h-1","h-7","h-K","h-4","h-10","h-3","h-6","h-8","h-Q"]
heart_king = "h-K"
linear_search(heart_cards,heart_king)
However, although this linear search algorithm is very simple and straightforward, it is often inefficient in real life situations. If the number of data is small like this time, there is no problem, but what if the data increases to 10,000, 100,000, 1 million? Isn't it a huge amount of time to check the data one by one?
Of the linear search list Maximum number of searches is N (N is the number of data) Average number of searches is N / 2 It will be. So, with a linear search algorithm, if you want to search 1 million pieces of data, you have to turn the cards up to 1 million times, and on average 500,000 times. It takes a lot of time
Next, let's change the theme of playing cards This time, only 10 of the heart playing cards 1 to K are arranged in ascending order (always arranged in ascending order). At this time, what would you do if you were asked "Please answer where the 8 playing cards of the heart are"?
Do you want to do a linear search again?
No, in fact, we can only use more efficient algorithms if we have the condition that the data is sorted in ascending order. It is called a binary search algorithm.
First, turn over the middle playing card from the playing cards Then 6 came out The number of playing cards we want to find is 8 Since the playing cards are arranged in ascending order, you can see that the target playing card exists on the right side of this middle playing card. Now turn over the playing cards in the middle on the right side Then 10 will come out This time it is smaller than this so you can see that it is on the left side When I turned over the playing cards in the middle again, I found it safely.
In other words, binary search (also called binary search) is an algorithm that finds the desired data by halving the sorted elements and comparing whether the desired data is in front or behind. Let's replace it with a program
binary_search.py
# coding: utf-8
# Here your code !
def binary_search(card_list, card):
low = 0
high = len(card_list) - 1
print(high)
while low <= high:
mid = (low + high) // 2
#print(mid)
#print(card_list[mid])
if card_list[mid] == card:
print("{0}Second{1}There is".format(mid,card))
return
elif card_list[mid] < card:
low = mid + 1
else:
high = mid - 1
return
if __name__ == '__main__':
heart_cards = [1,2,4,5,6,8,9,10,12,13]
heart_eight = 8
binary_search(heart_cards, heart_eight)
The maximum number of searches in the linear search list is N (N is the number of data), and the average number of searches is N / 2. It was. On the other hand, the binary search algorithm Maximum number of searches is log2N + 1 The average number of searches is log2N Will be
In other words, when searching for 1 million pieces of data with the 2-minute search algorithm, it is only necessary to turn the Trump 21 times at the maximum and 20 times on average. Look back at the time when you were flipping cards up to 1 million times during the search algorithm. It's much more efficient than when doing a linear search.
[Calculation site useful for daily life and practice] Logarithmic function
However, as I explained at the beginning, this 2-minute search algorithm cannot be used unless the data is always aligned! If you can understand this far, it's natural. This two-minute search algorithm is valid because there is a condition that the data is always the smallest on the left side and larger on the right side.
However, in reality, the data in the world is rarely aligned by nature.
So what should I do?
The sort algorithm comes into play in such a case.
The sorting algorithm is an algorithm that sorts randomly and irregularly arranged data groups in ascending order, descending order, and so on.
This is the end of the explanation of the search algorithm.
"I want to get some desired data from the data group! When there was a problem We can use a linear search algorithm This is a simple, straightforward algorithm that even beginners can solve this problem.
However, this linear search algorithm has another problem. That it is inefficient This algorithm has the potential to search 1 million times for 1 million pieces of data.
And the solution to this problem is the 2-minute search algorithm.
"I want to efficiently obtain data of a certain purpose from the data group! ], You can use this 2-minute search algorithm.
But again, this two-minute search algorithm has another problem. That is, it cannot be used unless the data is aligned. This two-minute search algorithm can be used because it is assumed that the data are sorted in ascending and descending order.
And the sorting algorithm that will be introduced later solves this problem. There are actually many types of this sorting algorithm. Depending on each, the efficiency may differ or they may be used in combination.
However, each sorting algorithm has one purpose.
Aligning disjointed data groups
Let's start from the next
Also for other search algorithms Hash search algorithm There is something called. I will omit it this time I hope I can introduce you somewhere again
[[Paiza development diary] List of algorithm types that IT engineers should know, which cannot be heard now](http://paiza.hatenablog.com/entry/2015/10/19/IT%E3%82%A8%E3 % 83% B3% E3% 82% B8% E3% 83% 8B% E3% 82% A2% E3% 81% AA% E3% 82% 89% E7% 9F% A5% E3% 81% A3% E3% 81 % A6% E3% 81% 8A% E3% 81% 8D% E3% 81% 9F% E3% 81% 84% E3% 80% 81% E4% BB% 8A% E6% 9B% B4% E8% 81% 9E % E3% 81% 91% E3% 81% AA% E3% 81% 84% E3% 82% A2)
Recommended Posts