女性向けエンジニアスクール
3秒でわかる
データが増えたときに処理時間やメモリがどう伸びるかを表す指標。手元の少ない件数では分からない性能の差を、実装する前に見積もるために使います。
もう少し詳しく
どういうものか
計算量は、入力の大きさ n に対して処理の手数がどう増えるかを表したものです。実行時間そのものではなく伸び方を見るため、計算機の速さや言語の違いに左右されません。表記には O 記法を使い、影響の小さい項と定数倍を落として O(n log n) のように書きます。
時間の計算量と空間の計算量があります。前者は手数、後者は追加で必要なメモリ量です。片方を減らすともう片方が増えることが多く、どちらを優先するかは要件次第になります。
なぜ必要か
10 件のテストデータでは、O(n) も O(n^2) も一瞬で終わります。差が出るのは本番のデータ量になってからです。n が 1000 なら 100 万回、n が 10 万なら 100 億回となり、後者は数分から数時間かかります。実装してから気付くと作り直しになるため、書く前に見積もります。
具体例
# O(n^2) 二重ループで全組み合わせを比べる
def has_pair_slow(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return True
return False
# O(n) 見た値を集合に覚えておく
def has_pair_fast(nums, target):
seen = set()
for x in nums:
if target - x in seen:
return True
seen.add(x)
return False下の書き方は、メモリを n 個分余計に使う代わりに手数を大幅に減らしています。時間と空間の交換の典型例です。
つまずきやすいところ
ループが 1 つしか見えないのに、実際は O(n^2) というのが最も多い誤りです。ループの中で list.index() や in をリストに対して呼ぶと、その 1 行が内部で n 回走ります。上の例で seen を集合ではなくリストにすると、見た目は同じでも O(n^2) に戻ります。
定数倍を軽視しすぎるのも実務では失敗します。O 記法は定数を無視しますが、n が数百程度なら定数倍の小さい単純な実装のほうが速いことは珍しくありません。
似た用語との違い
O 記法は上限を表します。最良の場合を語りたいときは別の記法を使いますが、実務では最悪と平均を押さえておけば足ります。
覚え方
「n を 10 倍にしたら何倍になるか」で考えます。O(n) なら 10 倍、O(n^2) なら 100 倍です。
