計算量の問題の解き方
飛岡拓希公開
計算量は、一番内側の行が何回実行されるかで決まります。 いきなり式にせず、n = 4 くらいの小さい数で実際に数えてから、n の式にします。
まず小さい n で数える
次のプログラムで、count ← count + 1 が何回実行されるかを考えます。
for (i を 1 から n まで 1 ずつ増やす)
for (j を i から n まで 1 ずつ増やす)
count ← count + 1
endfor
endforn = 4 として、i ごとに内側のループが何回回るかを書きます。
i = 1: j = 1, 2, 3, 4 → 4回 i = 2: j = 2, 3, 4 → 3回 i = 3: j = 3, 4 → 2回 i = 4: j = 4 → 1回 合計 10回
4 + 3 + 2 + 1 なので、n のときは n + (n − 1) + … + 1 = n(n + 1) ÷ 2 回です。 n = 4 を入れると 10 になり、数えた結果と合います。式を作ったら、数えた n を入れて合うかを必ず確かめます。1つずれた式（n(n − 1) ÷ 2 など）は、ここで落とせます。
O記法は、一番大きい項だけを残す
n(n + 1) ÷ 2 を展開すると、n² ÷ 2 + n ÷ 2 です。O記法では、n が大きくなったときに一番効く項だけを残し、係数も外します。n² ÷ 2 が残り、÷ 2 を外して O(n²) です。
n = 1000 のとき、n² ÷ 2 は 500,000、n ÷ 2 は 500 です。後ろの項は全体の 0.1% しかないので、無視しても増え方の傾向は変わりません。 「内側のループが i から始まるので半分になる」と考えて O(n²) より小さい選択肢を選ぶのは、よくある間違いです。 半分は係数で、O記法では消えます。
半分ずつ減るループは log n 回
次のループは、何回回るでしょうか。
k ← n while (k > 1) k ← k ÷ 2 // 小数点以下切捨て count ← count + 1 endwhile
n = 16: 16 → 8 → 4 → 2 → 1 4回 n = 32: 32 → 16 → 8 → 4 → 2 → 1 5回
n が2倍になっても、回数は1回しか増えません。16 は 2 を4回掛けた数、32 は5回掛けた数なので、回数は log₂ n です。O記法では O(log n) と書きます。 二分探索が速いのは、探す範囲がこの形で半分ずつ減るからです。
n が2倍になると、何倍になるか
「要素数が2倍になると、処理時間はおよそ何倍か」と聞く問題もあります。オーダーごとに覚えておくと速いです。
| オーダー | n が2倍で | 代表的な処理 |
|---|---|---|
| O(1) | 変わらない | 配列の要素番号を指定して読む |
| O(log n) | 1回ぶん増える | 二分探索 |
| O(n) | 2倍 | 先頭から順に探す（線形探索） |
| O(n log n) | 2倍より少し多い | マージソートなどの効率のよい整列 |
| O(n²) | 4倍 | バブルソート、選択ソート |
ただし、表は覚えるためではなく、選択肢を絞るための目安です。 問題のプログラムが表の名前と同じでも、書き方によって回数は変わります。最後は、上のように小さい n で数えて確かめてください。
ループが2つ並んでいるときは、足す
二重ループ（入れ子）は回数を掛けますが、ループが上下に並んでいるだけなら、回数を足します。n 回のループのあとに、もう1つ n 回のループがあれば、合わせて 2n 回で、係数を外して O(n) です。 入れ子なら n × n = n² 回で、O(n²) になります。 字下げを見て、入れ子か並びかを最初に確かめます。
計算量の問題:
- 整列済み二次元配列を探索する計算量を求める（難易度 4・登録なしで解けます）
- 挿入整列の比較回数と計算量のオーダーを求める（難易度 3・登録なしで解けます）
ほかの分野の解き方
解いたあとに解説を読む
このサイト（極とれ）の問題は、解いたあとにトレースの手順と、 選択肢ごとに「なぜ違うか」が開きます。登録なしで解けます。
計算量の練習問題を見る記法は IPA が公開しているサンプル問題・公開問題の記述形式に基づいています。 出題形式は改訂されることがあるため、受験の際は IPA の公表内容をご確認ください。
この記事について
書いているのは飛岡拓希です。基本情報技術者試験の科目B だけを扱う学習サービス「極とれ」を 1人で作って運営しています。試験には高校3年生のときに合格しました（そのときの記録）。
数字を載せるときは、出典の資料を自分で開いて数えた値だけを使い、いつ時点のものかを本文に書いています。 誤りに気づいたら goku.tore9@gmail.com までお知らせください。読んだ感想はフォームからも送れます。