C language learned by suffering

C language learned by suffering

An algorithm is a procedure, or formula, for solving a certain problem.
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.


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.

Computers are pure theory, so unlike the real world, there are no physical constraints.
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.


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


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.


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
1	1
5	3000
10	362880000
12	68976230400
14	17086945080000
15	294226732800000
20	9731608033000000000000000

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
1	1
5	25
15	225
25	400
50	2500
100	10000

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.

In the previous section, we compared the number of calculations in order to compare the computational complexity of algorithms.
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.


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.

At first glance, data structure sounds like a word that has nothing to do with algorithms.
However, data structures and algorithms are inseparable.


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.