MMGames
Read it right next to your computer.
Book version bitter C
learn through sufferingC Language
learn through sufferingC Language
Algorithm Overview
What is an algorithm?
An algorithm is a procedure for solving a problem, in other words, a formula.
More precisely, it refers to a computational method consisting of a finite number of clear steps repeated a finite number of times.
Clear procedures mean exactly what they sound like.
As explained in Part 0, computers require clear instructions.
"“Get some kimchi out of the refrigerator” is an ambiguous command,"
"“18-degree rotation, 182 centimeters forward, 36-degree rotation, 90-degree arm raise…” is a clear command."
"The phrase 'a finite number of steps' is a somewhat peculiar expression."
It's generally unlikely that the procedure would be infinite, so you don't need to worry too much about it.
Iterative computation, at its core, means that the calculation will eventually terminate.
There's no end in sight if we keep repeating endless calculations.
Even infinite calculations of pi are forcibly terminated after a certain degree of calculation.
These conditions are necessary when solving problems by having a computer perform the calculations.
Normally, when humans solve problems, they rely to some extent on experience and intuition.
Since computers lack that functionality, a clear procedure is necessary.
The algorithm is, in principle, language-independent.
You can use the same algorithm in C, Java, or BASIC.
More precisely, it refers to a computational method consisting of a finite number of clear steps repeated a finite number of times.
キーワード
【algorithm】
明確に定義された有限個の規則の集まりであって、
有限回適用することによって問題を解くもの。
(JIS(day本工業規格)より)
Clear procedures mean exactly what they sound like.
As explained in Part 0, computers require clear instructions.
"“Get some kimchi out of the refrigerator” is an ambiguous command,"
"“18-degree rotation, 182 centimeters forward, 36-degree rotation, 90-degree arm raise…” is a clear command."
"The phrase 'a finite number of steps' is a somewhat peculiar expression."
It's generally unlikely that the procedure would be infinite, so you don't need to worry too much about it.
Iterative computation, at its core, means that the calculation will eventually terminate.
There's no end in sight if we keep repeating endless calculations.
Even infinite calculations of pi are forcibly terminated after a certain degree of calculation.
These conditions are necessary when solving problems by having a computer perform the calculations.
Normally, when humans solve problems, they rely to some extent on experience and intuition.
Since computers lack that functionality, a clear procedure is necessary.
The algorithm is, in principle, language-independent.
You can use the same algorithm in C, Java, or BASIC.
Algorithm performance
Computers exist in a purely theoretical world, free from the physical constraints that characterize the real world.
Therefore, even when solving the same problem, there are truly a variety of approaches we can consider.
However, naturally, there are some excellent methods and some that are not among the various ways.
Here, the question of where to determine the superior method, or the issue of performance evaluation, arises.
"The following criteria are commonly used to compare the performance of algorithms."
The most noteworthy aspect among these is undoubtedly the computational complexity.
However, the other metrics don't show a significant difference based on the algorithm.
The difference in computational complexity can be [as vast as the difference between heaven and earth] when algorithms are different.
An interesting example illustrating this is the issue of stable marriage.
This problem can be simply explained as follows:
Let's consider how to solve this problem using a computer.
The first thing that comes to mind is to check if there are any cheaters for all combinations.
Of course, you can still arrive at the answer this way.
However, the more men and women go on blind dates, the longer it takes.
"It takes a few seconds for 10 people, but over 30 minutes for 14, and over a day for 15 or more."
Calculations will never end as long as humanity exists, even if the group size reaches twenty.
The total number of possible pairings can be calculated using the factorial of the number of people.
Furthermore, in infidelity checks, you must verify infidelity for the square of the number of people.
"That means this algorithm will require a calculation of factorial of the number of people multiplied by the square of the number of people."
Based on this, I will put the number of people and calculation iterations in a table.
We've observed that the number of calculations increases unbelievably dramatically as the number of people increases.
It's a problem if it takes millions of years to calculate.
Is there a way to reduce the computational complexity to make the calculation finish faster?
In fact, you don't need to check all the combinations.
First, the man proposes to his first choice woman.
At this time, if the woman is single or has a low opinion of her current partner, she will become engaged to a new man.
And the rejected man will propose to a woman of lower status than the woman he proposed to just now.
"Essentially, men lower their standards while women raise theirs in the selection process."
In this algorithm, N men court N women, so the number of iterations is the square of the number of people.
Based on this, I will put the number of people and calculation iterations in a table.
The number of calculations has decreased dramatically compared to before.
"This algorithm can calculate even matchmaking for 100 people in just seconds."
"That's how different algorithms can lead to results that take seconds or never finish, even after millions of years."There's quite a difference.
Therefore, the performance of algorithms is primarily judged by computational complexity.
Therefore, even when solving the same problem, there are truly a variety of approaches we can consider.
However, naturally, there are some excellent methods and some that are not among the various ways.
Computers and Religion
実はコンピュータ業界にも宗教的なところがあります。
というのも、物理的な制約を無視し、実にさまざまな考え方ができてしまうからis.
そのため、同じことをやるにしても人によって方法がまったく異なり、
場合によっては、どの方法を信じるのか、というレベルの争いになるためis.
というのも、物理的な制約を無視し、実にさまざまな考え方ができてしまうからis.
そのため、同じことをやるにしても人によって方法がまったく異なり、
場合によっては、どの方法を信じるのか、というレベルの争いになるためis.
Here, the question of where to determine the superior method, or the issue of performance evaluation, arises.
"The following criteria are commonly used to compare the performance of algorithms."
Algorithm performance
Computational complexity(少ないほど優秀)
メモリ使用量(少なく済むほど優秀)
計算の精度(正確に計算できるほど優秀)
プログラムの作りやすさ(簡単に作れるほど優秀)
メモリ使用量(少なく済むほど優秀)
計算の精度(正確に計算できるほど優秀)
プログラムの作りやすさ(簡単に作れるほど優秀)
The most noteworthy aspect among these is undoubtedly the computational complexity.
However, the other metrics don't show a significant difference based on the algorithm.
The difference in computational complexity can be [as vast as the difference between heaven and earth] when algorithms are different.
An interesting example illustrating this is the issue of stable marriage.
This problem can be simply explained as follows:
A stable marriage
Several single men and women participated in a group matchmaking event and rated their feelings towards each other.They cheat on their spouses because they believe they prefer someone else.Find them all a marriage combination without the worry of infidelity.
Let's consider how to solve this problem using a computer.
The first thing that comes to mind is to check if there are any cheaters for all combinations.
Of course, you can still arrive at the answer this way.
However, the more men and women go on blind dates, the longer it takes.
"It takes a few seconds for 10 people, but over 30 minutes for 14, and over a day for 15 or more."
Calculations will never end as long as humanity exists, even if the group size reaches twenty.
That's why it's taking so long – because it's checking every possible combination.
The total number of possible pairings can be calculated using the factorial of the number of people.
キーワード
【factorial】
1x2x3x4x5x6x7x8x9x10..... という計算のこと。
数が多くなるとねずみ算以上に膨大な数になる。
Furthermore, in infidelity checks, you must verify infidelity for the square of the number of people.
"That means this algorithm will require a calculation of factorial of the number of people multiplied by the square of the number of people."
Based on this, I will put the number of people and calculation iterations in a table.
| 人数 | 計算回数 |
|---|---|
| 1 | 1 |
| 5 | 3000 |
| 10 | 362880000 |
| 12 | 68976230400 |
| 14 | 17086945080000 |
| 15 | 294226732800000 |
| 20 | 973160803300000000000 |
We've observed that the number of calculations increases unbelievably dramatically as the number of people increases.
It's a problem if it takes millions of years to calculate.
Is there a way to reduce the computational complexity to make the calculation finish faster?
In fact, you don't need to check all the combinations.
First, the man proposes to his first choice woman.
At this time, if the woman is single or has a low opinion of her current partner, she will become engaged to a new man.
And the rejected man will propose to a woman of lower status than the woman he proposed to just now.
"Essentially, men lower their standards while women raise theirs in the selection process."
In this algorithm, N men court N women, so the number of iterations is the square of the number of people.
Based on this, I will put the number of people and calculation iterations in a table.
| 人数 | 計算回数 |
|---|---|
| 1 | 1 |
| 5 | 25 |
| 15 | 225 |
| 25 | 400 |
| 50 | 2500 |
| 100 | 10000 |
The number of calculations has decreased dramatically compared to before.
"This algorithm can calculate even matchmaking for 100 people in just seconds."
"That's how different algorithms can lead to results that take seconds or never finish, even after millions of years."There's quite a difference.
Therefore, the performance of algorithms is primarily judged by computational complexity.
About other criteria
The memory usage and computational accuracy also depend on the algorithm.
However, it's not a difference of that magnitude, so reducing the computational complexity is the most important thing.
However, ease of programming is prioritized, and computational complexity may not always be a major concern.
The more advanced an algorithm is, the longer it takes to implement and the more prone it is to bugs.
Modern computers are so fast that sometimes a slightly slower algorithm is not a problem.
Sometimes, choosing the simpler option is the safer bet.
However, it's not a difference of that magnitude, so reducing the computational complexity is the most important thing.
However, ease of programming is prioritized, and computational complexity may not always be a major concern.
The more advanced an algorithm is, the longer it takes to implement and the more prone it is to bugs.
Modern computers are so fast that sometimes a slightly slower algorithm is not a problem.
Sometimes, choosing the simpler option is the safer bet.
O notation
In the preceding section, we compared the number of operations to compare the computational complexity of algorithms.
"It's more intuitive to compare it based on the actual time it takes when run on a computer."
Why did you bother comparing the number of calculations?
This is because the time will vary depending on the computer executing it.
Naturally, a high-performance computer can calculate faster than a low-performance one.
There's also the option of always comparing on the same computer.
In the ever-evolving world of computers, you simply can't keep using the same machine indefinitely.
"It also leads to unfairness because there's a compatibility issue with computers and algorithms."
Therefore, in algorithm comparisons, we base the comparison on the number of computations.
However, it's not very meaningful to ask for the exact number of times each line is calculated.
The time it takes for the algorithm to compute is due to the repetitive processing.
The time spent on non-iterative parts is so short that it can be ignored.
In essence, you can get a general idea of an algorithm's computational complexity by comparing the number of repetitions.
However, as with the algorithm described in the preceding paragraph, the amount of calculation increases as the source data grows.
There are algorithms that can increase the number of repetitions enormously.
Therefore, rather than comparing the number of repetitions itself,
The extent to which the number of iterations increases is crucial with respect to the growth of the source data.
For these reasons, the computational complexity of algorithms is expressed using O(Big O) notation.
In O notation, if the number of repetitions is proportional to n for n data points, it is expressed as O(n).
"However, even when the number of iterations is 2n for n data points, it is expressed as O(n)."
The effect of integer multiples is negligible compared to squares, so we will ignore them.
In O notation, the primary focus is on how the growth rate changes when dealing with a very large number of data points.
For example, the former algorithm can be expressed as O(n!) using Big O notation, while the latter is O(N^2).
The number of calculations for the former was "factorial of the number of people times the square of the number of people".
Compared to factorials, squaring is insignificant, so we can disregard it.
Using Big O notation to determine time complexity, the values are primarily as follows.
"The algorithm on the right means that the computation will slow down exponentially as the number of data points increases."
For an O(1) algorithm, the computation time remains the same regardless of the amount of data.
For an O(n) algorithm, the computational complexity is directly proportional to the number of data points.
For an algorithm with a time complexity of O(n^2), the computational cost is directly proportional to the square of the number of data points.
Using Big O notation, you can understand an algorithm's performance without running it on a computer.
And it allows us to understand how much slower the calculations become as the data size increases.
It is extremely helpful in assessing algorithm performance.
"It's more intuitive to compare it based on the actual time it takes when run on a computer."
Why did you bother comparing the number of calculations?
This is because the time will vary depending on the computer executing it.
Naturally, a high-performance computer can calculate faster than a low-performance one.
There's also the option of always comparing on the same computer.
In the ever-evolving world of computers, you simply can't keep using the same machine indefinitely.
"It also leads to unfairness because there's a compatibility issue with computers and algorithms."
Therefore, in algorithm comparisons, we base the comparison on the number of computations.
However, it's not very meaningful to ask for the exact number of times each line is calculated.
The time it takes for the algorithm to compute is due to the repetitive processing.
The time spent on non-iterative parts is so short that it can be ignored.
In essence, you can get a general idea of an algorithm's computational complexity by comparing the number of repetitions.
However, as with the algorithm described in the preceding paragraph, the amount of calculation increases as the source data grows.
There are algorithms that can increase the number of repetitions enormously.
Therefore, rather than comparing the number of repetitions itself,
The extent to which the number of iterations increases is crucial with respect to the growth of the source data.
For these reasons, the computational complexity of algorithms is expressed using O(Big O) notation.
キーワード
【O notation】
"The number of repetitions was asymptotically determined based on the data size."
In O notation, if the number of repetitions is proportional to n for n data points, it is expressed as O(n).
"However, even when the number of iterations is 2n for n data points, it is expressed as O(n)."
The effect of integer multiples is negligible compared to squares, so we will ignore them.
In O notation, the primary focus is on how the growth rate changes when dealing with a very large number of data points.
For example, the former algorithm can be expressed as O(n!) using Big O notation, while the latter is O(N^2).
the squaring symbol
"Because it's difficult to represent exponents like 'squared' in computer fonts, we use the symbol '^2'."
The number of calculations for the former was "factorial of the number of people times the square of the number of people".
Compared to factorials, squaring is insignificant, so we can disregard it.
Using Big O notation to determine time complexity, the values are primarily as follows.
Computational complexity
1、log2n、n、nlog2n、n^2、2^n、n!
"The algorithm on the right means that the computation will slow down exponentially as the number of data points increases."
For an O(1) algorithm, the computation time remains the same regardless of the amount of data.
For an O(n) algorithm, the computational complexity is directly proportional to the number of data points.
For an algorithm with a time complexity of O(n^2), the computational cost is directly proportional to the square of the number of data points.
Using Big O notation, you can understand an algorithm's performance without running it on a computer.
And it allows us to understand how much slower the calculations become as the data size increases.
It is extremely helpful in assessing algorithm performance.
Worst-case scenario
ここまではComputational complexityと書いてきましたが、正確には最大Computational complexityis.
同じalgorithmであっても、そのComputational complexityはデータによって変わります。
たとえば、すべてを調べる遅いalgorithmで２０人の結婚を計算した場合でも、
もしも解答が組み合わせのすぐ始めにあったとしたら、一瞬で答えがでます。
逆に、解答が組み合わせの最後の方にあるとしたら、何千yearもかかります。
algorithmでは、最大Computational complexityを重視しています。
最大Computational complexityが遅いと、計算が終わらない最悪の事態になりかねないためis.
なお、平均的なComputational complexityを数学的に求めることは困難is.
同じalgorithmであっても、そのComputational complexityはデータによって変わります。
たとえば、すべてを調べる遅いalgorithmで２０人の結婚を計算した場合でも、
もしも解答が組み合わせのすぐ始めにあったとしたら、一瞬で答えがでます。
逆に、解答が組み合わせの最後の方にあるとしたら、何千yearもかかります。
algorithmでは、最大Computational complexityを重視しています。
最大Computational complexityが遅いと、計算が終わらない最悪の事態になりかねないためis.
なお、平均的なComputational complexityを数学的に求めることは困難is.
Data Structures
"Data structures might sound like a term unrelated to algorithms at first glance."
However, data structures and algorithms are inextricably linked.
A data structure refers to the way information is organized and stored.
Actually, there's a data structure that's already been explained.It is an array and a struct.
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 them represent information that is difficult to express with ordinary variables.
In algorithms, you need to calculate data to produce an answer.
The way you store data at this time is crucial.
Storing data in an unnatural way can be time-consuming to manage.
Sometimes, the data structure itself can even be considered an algorithm.
However, data structures and algorithms are inextricably linked.
キーワード
【Data Structures】
Ways of representing information.
A data structure refers to the way information is organized and stored.
Actually, there's a data structure that's already been explained.It is an array and a struct.
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 them represent information that is difficult to express with ordinary variables.
In algorithms, you need to calculate data to produce an answer.
The way you store data at this time is crucial.
Storing data in an unnatural way can be time-consuming to manage.
Sometimes, the data structure itself can even be considered an algorithm.
About This Site
Learning C language through suffering (Kushi C) is
This is the definitive introduction to the C language.
It systematically explains the basic functions of the C language.
The quality is equal to or higher than commercially available books.