プログラムの計算量を求める

Qiitaにわかりやすい記事がたくさんあるので、そっちを参照するのをおすすめします

ここではざっくりと大雑把にしかやらないよ

求め方

O(N)の例

以下のような、1から与えられた数までの数字を順番に足すプログラムがあったとする

code:py

# nは1以上の整数とする

def sum(n: int) -> int:

result = 0

for i in range(1, n + 1):

# iの範囲: 1 <= i <= n

result += i

return result

結論から言うと、このプログラムの計算量は$ O(N)となる

途中でN回のループが挟まれているため

いやfor文の上下にもresult = 0とかreturn resultとかあるから、$ O(N+2)が正しいんじゃないの？とか思うかもしれないが、$ +2のような値はさして計算数には影響しないため、無視して良いことになっているらしい

Nが1なら1+2=3となって、結構影響しているように見えるかもしれないが、Nが100,000とかだったら100,000+2=100,002となり、あってもなくても大して変わらなくなる

他にも、定数倍（$ 2Nの$ 2）や最高次数以外の数（$ N^2+N+1の$ Nと$ 1）も含めなくて良いことになっているらしい

ここが詳しい

O(N^2)の例

もう1つ例を出す

code:py

def print_table(n: int) -> None:

for i in range(1, n + 1):

for j in range(1, n + 1):

print(f"{i} * {j} = {i * j}")

このプログラムは、N回のループが二重になっているため、$ N \times Nで$ O(N^2)となる