What is an algorithm?
A little more strictly, it is a method of calculation in which a definite and finite number of steps are repeated a finite number of times.
A collection of a finite number of well-defined rules
A problem that is solved by applying it a finite number of times.
(From JIS (Japan Industrial Standards))
Clear procedure means exactly what it says.
As explained in Part 0, computers require clear instructions.
A command like, "Go get kimchi from the fridge," is an ill-defined command.
Rotate 18 degrees, move forward 182 centimeters, rotate 36 degrees, raise arm 90 degrees..." is a clear command.
Finite number of steps is a somewhat curious expression.
It is generally hard to imagine an infinite number of procedures, so don't worry too much about it.
A calculation that is repeated a finite number of times means, in other words, that the calculation will always end at some point.
There is no end to the endless repetition of endless calculations.
Even the endless calculation of pi is forced to end when it has been calculated to a certain extent.
These conditions are necessary when solving problems by letting the computer do the calculations.
Normally, when humans solve problems, we rely to some extent on experience and intuition.
Since computers do not have such capabilities, a clear procedure is necessary.
In principle, the algorithm does not depend on the programming language.
The same algorithm can be used in C, Java, or BASIC.
Therefore, a great variety of methods can be considered for solving the same problem.
Naturally, however, among the various methods, some are superior and others are not.
This is because it ignores physical constraints and allows for a great variety of ways of thinking.
Therefore, different people have very different ways of doing the same thing.
In some cases, the level of conflict is about which method to believe in.
The question is where to judge a method as superior, i.e., performance evaluation.
The following criteria are often used to compare the performance of algorithms
Memory usage (less is better)
Accuracy of calculation (the more accurate the calculation, the better)
Ease of programming (the easier it is to create, the better)
The most noteworthy aspect of this is the amount of calculation.
The other criteria, however, do not vary much from algorithm to algorithm.
The amount of computation is the only thing that makes the difference between heaven and earth between different algorithms.
An interesting example of this is the issue of stable marriage.
This problem can be briefly described as follows.
Let us consider how to solve this problem with a computer.
The first method that comes to mind is to check for cheating partners for all combinations.
This method, of course, can also provide an answer.
However, the more men and women you match, the more time it will take.
With 10 people it is a few seconds, but with 14 people it is more than 30 minutes, and with more than 15 people it is more than a day.
At 20 people, the calculation is no longer complete for the duration of human existence.
The reason why it takes so long is because all combinations are examined.
The total number of male-female combinations can be found by factorial of the number of people.
1x2x3x4x5x6x7x8x9x10..... The calculation that
The number is huge, more than mouse arithmetic.
In addition, the cheating confirmation must confirm cheating by the square of the number of people.
Then, this algorithm requires a calculation of "factorial of the number of persons x square of the number of persons" times.
Based on this, the table below shows the number of people and the number of calculations.
|Number of people
|Number of calculations
As the number of people increases, we find that the number of calculations increases to an incredibly extreme degree.
We don't want the calculations to take millions of years to complete.
Is there any way to reduce the amount of calculations so that they can be completed more quickly?
In fact, it is not necessary to examine every combination.
First, the man asks the woman of his first choice to marry him.
At this time, if the woman does not have a partner or if she does, she will be engaged to a new man if he is less favorable.
The rejected man then proposes to marry a woman one rank lower than the woman he just courted.
In other words, the man decides on a partner as he drops down the ranks, while the woman moves up the ranks.
In this algorithm, N men will propose to N women, so the number of calculations is the square of the number of people.
Based on this, the number of people and the number of calculations are shown in the table.
|Number of people
|Number of calculations
The number of calculations is much less than before.
With this algorithm, even a large matchmaking of 100 people can be calculated in a few seconds.
Thus, different algorithms may take a few seconds or millions of years to finish. The difference is as large as "a few seconds" or "a few million years".
For this reason, computational complexity is of paramount importance in algorithm performance.
However, the difference is not as great as the amount of computation, so reducing the amount of computation is most important.
However, sometimes the ease of programming is more important, and the amount of computation is not so important.
The more advanced the algorithm, the longer it takes to implement and the more likely it is to have bugs.
Modern computers are so fast that sometimes a slightly slower algorithm is not a problem.
Therefore, it is sometimes safer to choose the one that is easier to understand.
O (O) notation
Even though it's more intuitive to compare the actual time it took to run it on a computer.
Why did you bother to compare the number of calculations, etc.?
This is because, of course, the time varies depending on the computer that executes it.
Naturally, a high-performance computer and a low-performance computer can compute faster on the higher performance computer.
One way to do this is to always compare them on the same computer.
In the ever-evolving computer world, we cannot continue to use computers with the same performance.
Besides, it would be unfair because of the compatibility between the computer and the algorithm.
Therefore, we compare algorithms based on the number of calculations.
However, it is not that meaningful to find the number of times each row is calculated exactly.
It is the iterative part of the algorithm's calculation that takes the most time.
The time required for the non-repeating part is so short that it can be ignored.
In other words, by comparing the number of iterations, the algorithm's computational complexity can be roughly determined.
However, as with the algorithm in the previous section, as the data from which the calculations are made increases
There are some algorithms for which the number of iterations increases enormously.
Therefore, rather than comparing the number of iterations itself
It is important to note how much the number of iterations increases with respect to the increase in the source data.
For this reason, the O (O) notation is used for the computational complexity of the algorithm.
The asymptotically obtained value of the increase in the number of iterations relative to the number of data.
In O notation, if the number of iterations is proportional to n for n data, it is denoted as O(n ).
However, if the number of iterations is 2n for n data, it is still expressed as O(n).
Since the effect of integer doubling is negligible compared to squaring, etc., integer doubling is ignored.
This is because the O notation places the greatest emphasis on the degree of increase when the number of data is very large.
For example, if the algorithm in the previous section is expressed in O notation, the former is O(n!) and the latter is O(N^2).
The number of calculations for the former was "number of persons factorial x number of persons squared" times, while the number of calculations for the latter was
Squared is not much compared to factorial, so squared is ignored.
Calculating quantities in O notation yields the following main values.
The more the algorithm on the right, the slower the computation explodes as the number of data increases.
In the case of the o(1) algorithm, the calculation takes the same amount of time no matter how large the number of data.
For the o(n) algorithm, the computational complexity is directly proportional to the number of data.
For the o(n~2) algorithm, the computational complexity is directly proportional to the square of the number of data.
Using O notation, the performance of the algorithm can be determined without running it on a computer.
Moreover, because you can see how much slower the computation gets as the number of data increases
It is very useful in determining the performance of algorithms.
Even if the same algorithm is used, its computational volume will vary depending on the data.
For example, even if we compute 20 marriages with a slow algorithm that examines all
If the answer was right at the beginning of the combination, the answer would be given in an instant.
Conversely, if the answer is at the end of the combination, it would take thousands of years.
Algorithms emphasize maximum computational complexity.
This is because if the maximum computation is too slow, it could be the worst case scenario where the computation is not finished.
Note that it is difficult to mathematically determine the average computational complexity.
However, data structures and algorithms are inseparable.
A method of representing information.
Data structure refers to the form that information takes when it is stored.
In fact, there is a data structure that has already been described. They are arrays and structures.
Arrays represent multiple pieces of information by arranging multiple variables of the same type.
Structures group variables of different types together to represent related information.
These are simple data structures, but all of the information is difficult to express in ordinary variables.
In an algorithm, the data must be computed to give an answer, but
At this time, the method by which the data is stored is very important.
If data is stored in an unnatural way, it will take time to handle it.
In some cases, the data structure itself is even an algorithm.
About this Site
The C language (bitter C), which is learned by suffering, is
This is the definitive C language introductory site.
It systematically explains the basic functions of the C language and
It is as complete as or more complete than any book on the market.