forループの実行回数を返す

10 倍のデータで、10 倍待たされるのか

100件なら一瞬で終わったのに、10万件を流したら返ってこない。そんなとき、データが増えると何が起きるかを見積もる物差しが、ループの実行回数です。実行時間は機械や処理の中身で変わりますが、回数はコードから数えられます。

実際の秒数は測る必要があります。ただし、件数が増えたときの増え方は、測る前にも予想できます。まずはループ本体が何回動くかを、小さな数字で追ってみます。

終わりの値は含まれない

Pythonの range(n) は、0から n - 1 までの整数を順に取り出します。range(3) なら3個です。

for i in range(3):
    print(i)
# 出力は順に 0、1、2

3は出てきません。JavaScriptの i = 0; i < n; i++ も同じ範囲です。条件を i <= n にすると、0からnまでを含むのでn + 1回になります。元の range(n) や i < n なら、nが0以下のときは一度も動きません。

一定なのか、比例するのか

空でない配列の先頭を1回取り出すだけなら、10件でも100万件でも取り出す回数は1回です。この一定の増え方を O(1) と書きます。

全件を1回ずつ見るならn回です。件数が10倍になると回数も10倍になります。これが O(n) です。時間もおよそ10倍になるという見積もりは、1回の処理の重さが同じときに使えます。

Big-Oは増え方をまとめる

n回でも2n回でも、増え方は O(n) です。Big-Oから実際の秒数が決まるわけではありません。

例題で確かめる

商品が6件あり、全件を見るループを続けて2回行います。1回目が6回、2回目も6回なので、合計は 6 + 6 = 12 回です。商品が60件なら120回になります。件数が10倍になると回数も10倍なので、この処理は O(n) です。2回のループを並べても、2乗にはなりません。