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 $ (~). image.png

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

Recommended Posts

Algorithm learned with Python 8th: Evaluation of algorithm
Algorithm learned with Python 10th: Binary search
Algorithm learned with Python 5th: Fibonacci sequence
Algorithm learned with Python 9th: Linear search
Algorithm learned with Python 4th: Prime numbers
Algorithm learned with Python 19th: Sorting (heapsort)
Algorithm learned with Python 6th: Leap year
Algorithm learned with Python 12th: Maze search
Algorithm learned with Python 11th: Tree structure
Algorithm learned with Python 16th: Sorting (insertion sort)
Algorithm learned with Python 14th: Tic-tac-toe (ox problem)
Algorithm learned with Python 15th: Sorting (selection sort)
Algorithm learned with Python 17th: Sorting (bubble sort)
Algorithm learned with Python 18th: Sorting (stack and queue)
Implementation of Dijkstra's algorithm with python
Algorithm learned with Python 2nd: Vending machine
1. Statistics learned with Python 1-3. Calculation of various statistics (statistics)
Algorithm learned with Python 3rd: Radix conversion
1. Statistics learned with Python 1-2. Calculation of various statistics (Numpy)
"Principle of dependency reversal" learned slowly with Python
[Python3] Dijkstra's algorithm with 14 lines
1. Statistics learned with Python 2. Probability distribution [Thorough understanding of scipy.stats]
[Python] Object-oriented programming learned with Pokemon
Getting Started with Python Basics of Python
Perceptron learning experiment learned with Python
Python data structures learned with chemoinformatics
Life game with Python! (Conway's Game of Life)
Efficient net pick-up learned with Python
10 functions of "language with battery" python
1. Statistics learned with Python 1-1. Basic statistics (Pandas)
4th night of loop with for
Coexistence of Python2 and 3 with CircleCI (1.0)
Bookkeeping Learned with Python-The Flow of Bookkeeping-
Basic study of OpenCV with Python
March 14th is Pi Day. The story of calculating pi with python
Python algorithm
[Python] Reactive Extensions learned with RxPY (3.0.1) [Rx]
Basics of binarized image processing with Python
[Examples of improving Python] Learning Python with Codecademy
Execute Python script with cron of TS-220
Conditional branching of Python learned by chemoinformatics
Check the existence of the file with python
Clogged with python update of GCP console ①
Search the maze with the python A * algorithm
Easy introduction of speech recognition with Python
UnicodeEncodeError struggle with standard output of python3
Drawing with Matrix-Reinventor of Python Image Processing-
Recommendation of Altair! Data visualization with Python
Let's develop an investment algorithm with Python 1
Comparison of matrix transpose speeds with Python
Non-recursive implementation of extended Euclidean algorithm (Python)
Calculate the shortest route of a graph with Dijkstra's algorithm and Python
Source code of sound source separation (machine learning practice series) learned with Python
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
I tried hundreds of millions of SQLite with python
FizzBuzz with Python3
Introduction of Python
Scraping with Python
Prepare the execution environment of Python3 with Docker
Statistics with python
Automatic operation of Chrome with Python + Selenium + pandas