[Kenchon book to Python]-Chapter 2- "Train your problem-solving skills! Algorithms and data structures" I rewrote the posted code to Python!

Introduction

This article is Kencho-san's book, which contains many explanations of competitive programming, ** Train your problem-solving skills! Algorithms and data structures（けんちょんさん本）**について、掲載コードをPythonに翻訳したものを、備忘のためまとめたものです。

On this page, we will introduce the contents of Chapter 2! Please forgive me if there are any bugs.

See the following pages for links to other chapters. [Table of Contents Page] https://qiita.com/KevinST/items/002676619a583754bf76

code2.1 Computational complexity of single for statement

It's a problem that shows the amount of calculation of a single for statement. I also added the output.

code2-1.py

#Receive N from input
N = int(input())
count = 0

for i in range(N):
    count += 1

#Output result
print(count)

[Input example] 100 [Output example] 100

So-called $ O (N) $!

code2.2 Computational complexity of double for statement

This time it is the amount of calculation of the double for statement

code2-2.py

N = int(input())
count = 0
for i in range(N):
    for j in range(N):
        count += 1
print(count)

[Input example] 100 [Output example] 10000

So-called computational complexity $ O (N ^ 2 $)!

code2.3 Even enumeration

code2-3.py

N = int(input())
for i in range(N, 1, -2):
    print(i)

[Input example] 10 [Output example] 10 8 6 4 2

The amount of calculation is $ O (N) $.

code2.4 All enumeration for recent point pairs

code2-4.py

def calc_dist(x1, y1, x2, y2):
    return ((x1 - x2)**2 + (y1 - y2)**2)**0.5

#Receive input data
N = int(input())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())

#Initialize the desired value with a sufficiently large value
minimum_dist = 10000000.0

#Start exploration
for i in range(N):
    for j in range(i+1, N):
        dist_i_j = calc_dist(x[i], y[i], x[j], y[j])
        if dist_i_j < minimum_dist:
            minimum_dist = dist_i_j

print(minimum_dist)

[Input example] 4 1 1 2 2 12 66 18 31 [Output example] 1.4142135623730951

In the above example, --Recent point pairs are (1,1) (2,2) --The distance is $ \ sqrt2 $ --Computational complexity is $ O (N ^ 2) $ is.

Click here for Chapter 3 https://qiita.com/KevinST/items/4d04dc7369880670a63b