Big O記号：A-Level情報科学で実際に求められること

Big O記号はあらゆる主要なA-Level情報科学の仕様（AQA、OCR、Edexcel）に登場し、多くの学生がつまずきます。原因は数学が難しいからではなく、実際のコードと結びつけて見ることがないからです。これは試験問題に答える際に必要な知識と、ごたごた説明せずに答える方法を実践的に解説したものです。

Big O記号が実際に測定するもの

Big O記号はアルゴリズムの実行時間（またはメモリ使用量）が入力サイズ（通常nと呼ばれる）の増加に伴ってどのように増加するかを示します。秒単位のストップウォッチ測定ではありません。ハードウェアに依存せずにアルゴリズムを比較できるように、成長率を説明する方法です。

O(n)と書くとき、「入力を2倍にするとおおよそ作業も2倍になる」と言っています。O(n²)は入力を2倍にするとおおよそ作業が4倍になる、という意味です。試験官が求めるのはこの関係を見つけることであり、正確な演算回数ではありません。

確実に覚えるべき計算量

A-Levelで繰り返し出題される計算量はこれらです。

• O(1) – 定数時間。インデックスで配列要素にアクセス：arr[5]。配列の大きさは関係ありません。
• O(log n) – 対数時間。ソート済みリストに対するバイナリサーチ。各ステップで検索範囲が半分になります。
• O(n) – 線形時間。リストを1回だけループする、例えばリニアサーチで各要素を1回だけチェックする。
• O(n log n) – 線形対数時間。マージソートとクイックソート（平均ケース）はここに該当します。
• O(n²) – 2次時間。同じデータに対する入れ子ループです。これはバブルソート、挿入ソート、選択ソートが行うことそのものです。
• O(2ⁿ) – 指数時間。メモイゼーションなしのナイーブな再帰Fibonacci。急速に複雑になります。

疑似コードを見て一目でこれらのいずれかであると言えるようになるべきです。ほとんどこれが試験されるからです。

コードから計算量を読む

毎回機能する方法：ループをカウントしてnとの関係を見る。

# O(n) - 1つのループ、1回のパス
for i in range(n):
    print(i)

# O(n^2) - 入れ子ループ、両方ともnに関連
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - 各反復で検索空間が半分になる
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

内側のループの範囲がnに依存する入れ子ループはO(n²)です。見た目が少し異なっても（例えばfor j in range(i)がfor j in range(n)の代わりにあっても）やはり全体として2次です。ただし定数係数に差があります。

n まったく関係ないループに注意してください。入力サイズに関わらず常に10回実行されるループはO(1)です。ループがあっても関係ありません。試験官がこれをこっそり忍ばせるのが好きです。

よくあるソートアルゴリズムとそのBig O

2つの仕様を同時に組み合わせるので、これが試験の人気テーマです。ソートアルゴリズムと計算量です。

アルゴリズム	最良ケース	最悪ケース
バブルソート	O(n)	O(n²)
挿入ソート	O(n)	O(n²)
マージソート	O(n log n)	O(n log n)
バイナリサーチ	O(1)	O(log n)
リニアサーチ	O(1)	O(n)

マージソートの一貫性（最良ケースと最悪ケースが同じ計算量）は、大規模データセットではバブルソートより選ぶ理由を聞かれた場合に明確に言及する価値があります。バブルソートのO(n)の最良ケースは、パスでスワップが起こらないときの早期終了最適化でのみ適用されます。それを言及する場合は、一部の試験委員会がそれを期待しているため、その詳細に触れてください。

学生がマークを失う場所

最大のもの：書く