﻿ Overview of Algorithms - C Language Learned by Suffering
C language learned by suffering

### Algorithm Overview

##### What is an algorithm?
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.

Keywords.
##### Algorithm

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.
##### Algorithm Performance
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.

Computers and Religion
In fact, the computer industry is also religious.
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

Algorithm Performance
Computational complexity (less is better)
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.

Stable marriage
Several single men and women each made a group match and expressed their liking for each partner. They would cheat on each other if they were more favorable to each other than to their own marriage partner. Find a marriage combination where all of them do not have to worry about cheating.

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.

Keywords.
##### Factorial

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
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.

For other criteria
Memory usage and calculation accuracy also vary by algorithm.
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
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.

Keywords.
##### O notation

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).

Symbol of square
Since it is difficult to represent squares in computer letters, the symbol ^2 is used.

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.

amount of calculation
1, log2n, n, nlog2n, n^2, 2^n, n!

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.

Worst-case calculation
Up to this point, I have written "computational complexity," but it is precisely the maximum computational complexity.

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.

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

Keywords.
##### Data Structure

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.

Comment
COMMENT

Open the 💬 comment submission box.