女性向けエンジニアスクール
3秒でわかる
入力の件数が増えたとき処理時間がどう伸びるかを表す指標。O記法で書き、遅くなる処理を実装してしまう前に見当をつけるためのものさしです。
もう少し詳しく
どういうものか
時間計算量は、入力データの件数 n が増えたときに処理のステップ数がどう伸びるかを表したものです。実際の秒数ではなく伸び方の形を表すので、マシンの速さや言語の違いに左右されません。O(1) は件数が増えても一定、O(log n) は倍に増えても1ステップ増えるだけ、O(n) は比例、O(n log n) はソートの標準的な速さ、O(n^2) は二重ループ、O(2^n) は総当たりです。
なぜ必要か
10件のテストデータでは O(n) も O(n^2) も体感で差が出ません。差が出るのは本番でデータが10万件になったときです。n=100000 のとき O(n) が10万ステップなのに対し O(n^2) は100億ステップで、秒で終わる処理が数時間になります。実装前に計算量を見積もっておけば、この事故を書く前に避けられます。
具体例
同じ「重複があるか」の判定でも、書き方で計算量が変わります。
# O(n^2) 全ペアを比べる
def has_dup_slow(xs):
for i in range(len(xs)):
for j in range(i + 1, len(xs)):
if xs[i] == xs[j]:
return True
return False
# O(n) 見た値を集合に覚える
def has_dup_fast(xs):
seen = set()
for x in xs:
if x in seen:
return True
seen.add(x)
return Falsen が 10 万のとき、前者は数分、後者は一瞬で終わります。
つまずきやすいところ
定数倍を切り捨てるルールを忘れて、O(n) なら常に O(n log n) より速いと思い込む例があります。n が小さいうちは定数の大きいアルゴリズムのほうが遅く、実データでは逆転することもあります。もうひとつは、in の計算量が型で違う点です。Pythonでは list への in は O(n)、set と dict への in は平均 O(1) です。ループの中で list に in を書くと、気づかないうちに O(n^2) になります。
似た用語との違い
| 語 | 何を測るか |
|---|---|
| 時間計算量 | ステップ数の増え方 |
| 空間計算量 | 使うメモリ量の増え方 |
| 実測値 | 実際にかかった秒数 |
時間と空間はしばしば逆を向きます。計算結果を覚えておけば時間は縮みますが、その分メモリを使います。
覚え方
ループがひとつなら n、ループの中にループなら n の2乗、半分ずつ絞り込むなら log n、と入れ子の形で見当をつけます。
