[ Algorithm ]
It is a group of the rule of limited piece clearly defined.
The one to solve problem by applying limited times.
(From JIS (Japan Industrial Standards). )
- ..clause 1..: What is the algorithm?
- ..clause 2..: Performance of algorithm
- ..clause 3..: O ([o-]) notation
- ..clause 4..: Data structure
The algorithm is official of which the procedure to solve a certain problem.
The clear cut procedure is a meaning of the street.
[ Algorithm ]
It is a group of the rule of limited piece clearly defined.
The one to solve problem by applying limited times.
(From JIS (Japan Industrial Standards). )
The procedure of limited piece is a little mysterious expression.
You may not worry becoming of the procedure infinitely so much in general because it doesn't think easily.
The calculation that repeats limited times is that the calculation ends without fail some time.
There is no paulownia in the length and the repetition of the calculation that doesn't end indefinitely.
End the calculation of pi following infinity compulsorily at the stage calculated to some extent.
Whenever the computer is made to calculate and the problem is solved, these conditions are necessary.
To some degree when man solves the problem though it relies on the experience and Caen usually
Because the computer doesn't provide such a function, the clear cut procedure is needed without fail.
The algorithm must not depend on the programming language as a rule.
The same algorithm can be used even in C, Java, and BASIC.
It differs from the real world because the computer is the world of a pure theory, and there is no physical restriction.
Therefore, even when the same problem is solved, very various methods can be devised.
However, various methods also include an excellent method and a method not so naturally.
Here..where..excellent method..judge..in a word..performance assessment..problem..become.
[ Computer and religion ]
Actually, the computer industry is religious.
Because a physical restriction can be disregarded, and very various ideas be done.
Therefore, even if the same thing is done, the method is quite different depending on the person.
It is according to circumstances because of becoming the fight over the level which method to be believed.
Computational speed(It is ending early excellent. )After all, this point that should be paid attention is a computational speed.
Memory utilization(It is ending few excellent. )
Accuracy of calculation(It is computable accurately excellent. )
Easiness of program to make(It is excellent as it is possible to make it easily. )
The problem of stable marriage is an interesting example of showing this.
These problems are the following problems when easily explaining.
It explains easily though it doesn't introduce to a concrete program code.
[ Stable marriage ]
Each of several men and women the single put it out, and the group met with a view to marriage, and put out the favorability to each other party.
When favorabilities are higher than my marriage partners, each other has an affair with them.
Find the combination of the marriages about which it is not worried that all members of them have an affair.
The purpose is about why to take time like this to examine all the combinations.
The total of man and woman's combination can be requested by the factorial of the number of people.
Moreover, when fickleness is not confirmed by the second power of the number of people alone, it doesn't become it in the fickleness confirmation.
[ The floor multiplication ]
1x2x3x4x5x6x7x8x9x10 Calculate.
It becomes more than the geometric progression and it becomes a great number when increasing.
| Number of people | Calculation frequency |
|---|---|
| 1 | 1 |
| 5 | 3000 |
| 10 | 362880000 |
| 12 | 68976230400 |
| 14 | 17086945080000 |
| 15 | 294226732800000 |
| 20 | 973160803300000000000 |
Then, let's think this is sped up.
To begin with, all the combinations need not be examined.
First of all, the man proposes to a 1st choice woman.
At this time, engage it to a new man when the woman doesn't have the other party or the favorability is low even in case of being.
And, the [fura] [reta] man proposes from the woman to the woman under 1 rank who proposed ahead.
In a word, the woman decides the other party while raising the rank while dropping the rank by the man.
Because N person's man proposes to N person's woman in this algorithm, the calculation frequencies are the second power of the number of people.
Tabulate the number of people and the calculation frequency based on this.
| Number of people | Calculation frequency |
|---|---|
| 1 | 1 |
| 5 | 25 |
| 15 | 225 |
| 20 | 400 |
| 50 | 2500 |
| 100 | 10000 |
The computational speed is ..difference between the calculator and the super computer.. [demasu] according to the algorithm thus.
[ Super-efficient game machine and family computer ]
The family computer was actually a super-efficient game machine though it became a complete bytalk.
If you think the game watch of the family computer appearance became popular ahead a little
I think that the difference of the performance is understood.
Music and the sound effect can be sounded at the same time by resolution 256x224 (It is larger than the advance) and 16 colors.
Sprite (overlapping processing of the character) is installed with hardware.
It is a miracle to be able to put out hardware like this in not big industry the game but the age.
It is the one that it wants you to feature it by project X by all means.
[ Other standards ]
The memory utilization is also different depending on the algorithm.
The speed doesn't have the difference though it is 2-3 times necessary in a high-speed algorithm.
Though the accuracy of the calculation is also different depending on the algorithm
The speed doesn't have the difference accurately in most algorithms.
The unexpectedly important one is easiness of the program to make.
Because it takes time in a more advanced algorithm and the bug increases easily, too
Easy one is used if there is only a velocity differential of the extent that can be disregarded.
In the preceding clause, the computational speed of the algorithm was compared and the calculation frequencies were compared for the sake of comparison.
Though comparing it at the time that is executed with the computer and takes actually is more intuitive
Did you purposely compare it by the calculation frequency etc. why?
This is because time changes by the computer that executes it naturally.
On a computer with high performance and a low computer, naturally high one is computable fast.
Though there is a method of the comparison always with the same computer, too
In the world of a rapid progress computer, do not keep using the computer of the same performance.
And, it becomes unfair because there is compatibility of the computer and the algorithm, too.
Then, compare it in the comparison of algorithms based on the calculation frequency.
However, even if the frequency calculated accurately in each line is requested, it is not too significant.
It is a part that takes time in the calculation of the algorithm repeatedly processed.
The time of the part not repeated can be disregarded because it is very short.
In a word, if the frequencies are repeatedly compared, the computing time of the algorithm is roughly understood.
However, when the data of the calculation origin increases like the algorithm in the preceding clause
There is an algorithm that the frequency increases enormously repeatedly, too.
Therefore, ..the repetition comparison of the frequencies..
Whether how much the frequency increases repeatedly compared with an increase of the data of the calculation origin becomes important.
O([o-]) notation is used for the computational speed of the algorithm for such reasons.
In O notation, if the repetition do proportion of the frequency to n for the data of n piece, it is shown O(n).
[ O ([o-]) notation ]
Value in which an increase in frequency is repeatedly requested from data number asymptotic.
For instance, when the algorithm in the preceding clause is shown by O notation, Former..latter.
Though the calculation frequency of the former was times of "The second power of factorial × number of people of numbers of people"
[ Sign of the second power ]
Use the sign named ^2 because it doesn't show the second power easily in the computer character.
If the computational speed is requested by O notation, it becomes the following chiefly values.
1､log2n､n､nlog2n､n^2､2^n､n!When the data number increases in a right algorithm, it means the calculation slows explosively.
The performance of the algorithm is understood no execution with the computer when O notation is used.
Moreover, to understand how much to come to slow in calculating when the data number increases
It is very useful for the performance judgment of the algorithm.
[ The worst calculation ]
It is the maximum calculation time accurately though has written the computing time here.
The computing time changes depending on data even if it is the same algorithm.
For instance, even when you calculate the marriage of 20 people by a slow algorithm that examines everything
[Demasu] ..the answer at the moment.. when the answer is in the start of the combination soon.
Oppositely, it also takes thousands of years if the answer is.
In the algorithm, the maximum calculation time is valued.
It is because it is likely to become the worst situation in which the calculation doesn't end when the maximum calculation time is slow.
It is difficult to request an average computing time mathematically.
I ..word that seems to be unrelated to the algorithm seemingly.. hear it with the data structure.
However, the data structure and the algorithm are in an inseparable relation.
The data structure means what shape you take when information is memorized.
[ Data structure ]
Mode of expression of information
Though it is necessary to calculate data and to find an answer to a question in the algorithm
It is very important by what method to memorize data at this time.
It takes time for the treatment when data is memorized in unnatural shape.
According to circumstances, it is even when the data structure is an algorithm.
