Algorithm learned with Python 8th: Evaluation of algorithm

#Algorithm learned in Python

Introduction

Implement the basic algorithm in Python to deepen your understanding of the algorithm. The eighth is the evaluation of the algorithm. I will not implement it this time, but I will summarize the basics of how to evaluate the algorithm while learning the algorithm.

How do you evaluate the program?

Do you implement it, measure it with some data, try it one by one, and evaluate it?

It is easy to understand with a simple idea, but the following problems arise ・ Cannot be evaluated when designing a program ・ May depend on environment and language

So ... There is an idea of ​​** Computational Complexity **

Computational Complexity

There are various computational complexitys such as time complexity, spatial complexity, communication complexity, and circuit complexity.

Time complexity and spatial complexity are often used as evaluation indexes in programs. ** Time complexity **: Refers to processing time ** Spatial complexity **: Refers to how much storage capacity such as memory is required

Example) If you program with some Fibonacci sequences stored, the amount of time calculation can be reduced, but the amount of spatial calculation to be stored in advance increases.

Pseudo processing time

If the actual processing time $ [s] $ is measured, it may affect the execution environment. Therefore, the time required for that one process is set as a constant and proportional to the number of repetitions, and this is used as the amount of calculation. Catch and evaluate.

For example, consider performing the print process once by turning the for statement 50 times as follows.

for i in range(50):
    print(i)

At this time, if the processing time of one print is $ a $, the processing time of this program is considered to be $ a \ times50 $. If this is an arbitrary number of $ n $ times instead of 50, the processing time can be considered to be $ a \ times50 $.

n = 100 #Arbitrary number
for i in range(n):
    print(i)

It can be said that the program processing time is proportional to the number of data $ n $ for a certain process. Here are some other examples.

n = 100 #Arbitrary number
for i in range(n):
    for j in range(n):
        print(i)

In this case, the processing time is considered to be $ a \ times n \ times n = a \ times n ^ 2 $. (Proportional to $ n ^ 2 $)

n = 100 #Arbitrary number
for i in range(n):
    for j in range(n):
        for k in range(n):
            print(i)

When three fot statements are nested in this way, the processing time is considered to be $ a \ times n \ times n \ times n = a \ times n ^ 3 $. (Proportional to $ n ^ 3 $)

Multiplying a certain constant by the number of data $ n $ in this way, and considering how the processing time is related to the number of data as the processing time, is used as the pseudo processing time, and then This is the idea of ​​the order notation shown.

Order notation

The ratio of processing time for $ n $ data is expressed in the form of $ O $ (~).

Impressions

Until now, we have evaluated several algorithms by measuring the processing time in time [s], but knowing this order notation, it is true that it can depend on the environment and language. I thought that such a common index was important. However, if it is simply a relative evaluation of one algorithm and another method, I feel that it may be evaluated by the time actually taken, and there are also papers that actually evaluate by such a thing. I think that is the case. However, when it comes to the absolute evaluation of the algorithm itself (is the algorithm really good?), I think the order notation is easier to understand and more reliable. When I started learning python, I heard that "it is not good to turn the for statement too much", but I was convinced that this was the case.

References

Introduction to algorithms starting with Python: Standards and computational complexity learned with traditional algorithms Written by Toshikatsu Masui, Shoeisha