データ構造とアルゴリズム：Big O Notation (Big O 記法)

アルゴリズムの処理速度を可視化したもの。

O(log(n))

# O(log(n))
def func2(n):
    if n <= 1:
        return
    else:
        print(n)
        func2(n/2)
func2(10)

10
5.0
2.5
1.25

O(n)

# O(n)

def func3(numbers):
    for num in numbers:
        print(num)
        
func3(range(1,10))

1
2
3
4
5
6
7
8
9

O(n * log(n))

# O(n * log(n))
def func4(n):
    for i in range(int(n)):
        print(i, end=' ')
    print()

    if n <= 1:
        return
    func4(n/2)

func4(10)

0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 
0 1 
0 

O(n**2)

for文を２回回すと２乗になる

# O(n**2)
# for文を２回回すと２乗になる
def func5(numbers):
    for i in range(len(numbers)):
        for j in range(len(numbers)):
            print(numbers[i], numbers[j])
        print()

func5([1,2,3,4,5])

1 1
1 2
1 3
1 4
1 5

2 1
2 2
2 3
2 4
2 5

3 1
3 2
3 3
3 4
3 5

4 1
4 2
4 3
4 4
4 5

5 1
5 2
5 3
5 4
5 5