ステップ数で理解する Big-O

Big-O は入力の増加に対する仕事量の漸近的な上界を表します。機器に依存するミリ秒数ではありません。本レッスンは小さな関数の主要操作を数え、n を 4、8、16 と二倍にして、四つの増加パターンを比べます。

カウンターは走行距離計に似ています。時間ではなく仕事量を読み、加算一回、探索一回、添字の組一つで一つ進めます。本レッスンの関数と入力では、n が二倍になったとき、回数が不変なら O(1)、一つ増えれば O(log n)、二倍なら O(n)、四倍なら O(n²) のパターンになります。既知のアルゴリズムの規則を示す実験であり、有限回の測定だけで任意のアルゴリズムの計算量を証明するものではありません。

入力を二倍にする実験の仕組み

各モードは主要操作を数えやすい Python 関数を実行します。

• O(1)：get_last(arr) は arr[-1] を直接読み、配列を走査しません。
• O(log n)：find(arr, target) はソート済み配列の二分探索です。対象を全要素より大きくして、見つからない最悪ケースを使います。毎回範囲を約半分にし、本例の入力では n の倍増ごとに探索が一回増えます。
• O(n)：total(arr) は各要素を一度訪れ、回数は長さに等しくなります。
• O(n²)：count_pairs(arr) は入れ子のループで全 (i, j) を処理します。画面の一辺 n の格子は n² マスで、一辺を二倍にすると面積は四倍です。

測定モードはまず n = 4 を一操作ずつ実行し、何を数えるかを示します。次の n = 8 と n = 16 は一続きの走査に圧縮し、結果を同じ増加グラフへ加えます。三つの点、曲線、倍増表で関数の増加パターンを確認します。

五つ目は競走（Race）です。四つの関数が n = 16 を使い、共通の時計で一拍に一操作ずつ実行します。get_last は一拍目、find は五拍目、total は十六拍目に終了します。その時点で count_pairs は 256 操作中の 16 しか終えていません。最後のグラフは全測定に n·log n と 2ⁿ の破線を加え、O(1) < O(log n) < O(n) < O(n²) < … という増加率の順序を示します。

ステップごとの解説

既定は競走です。四レーンとも n = 16 で、一拍に一操作ずつ進みます。

1. 0 拍目：開始。 四つが同時に出発し、どれが先に終わるかを比べます。
2. 1 拍目：O(1) が終了。 get_last は末尾を一度読み、他の十五要素を読みません。
3. 2–5 拍目：O(log n) が終了。 find が範囲を狭め、五回目の探索後に範囲が空になります。十六要素に対して五回です。
4. 6–16 拍目：O(n) が終了。 total はちょうど n 回訪れます。count_pairs はまだ 16／256 操作です。
5. 残り：O(n²) が続く。 全 256 組を処理して終わります。n = 16 で total の 16 倍の操作が必要で、n を二倍にするたび比率も二倍になります。
6. グラフへ集約。 各レーンの倍増実験が四つの測定曲線になります。O(1) は水平を保ち、O(n²) は上へ伸びます。
7. 増加率の比較。 n·log n と 2ⁿ の参考線を加えます。前者はマージソートなどに現れ、O(n) と O(n²) の間です。後者は十分大きな入力で、ここにある多項式の関数より速く増えます。

この順序は増加率の比較です。競走の終了順は、一操作一拍という共通のモデルにも依存します。個別モードでは n = 4 から 8、16 と測り、不変、+1、×2、×4 を確認できます。O(n) を最後まで再生すると、破線の 2n + 3 が現れます。傾きと位置は変わっても、線形のままです。

計算量で定数を省く理由

2n + 3 のように、各要素で固定回数の仕事を増やすと傾きが変わり、固定の準備や後処理を加えると上へずれます。線形という分類は変わりません。Big-O は入力が十分大きいときの上界に注目し、固定の倍率と低次項を省きます。

log₂ n と log₁₀ n は定数倍しか違わないため、どちらも O(log n) です。本レッスンでは、訪問、探索、添字の組という主要操作を数え、その一回に伴う固定の仕事を定数因子に含めます。

これは小さい入力での実際の速さを保証しません。n = 4 では count_pairs が 16 回、total が 4 回です。n = 16 で比率は 16 倍になり、倍増ごとに比率も増えます。固定の定数は小さい入力での比較を変えても、異なる増加の次数をいつまでも打ち消すことはできません。

境界ケース

• 最悪ケースは選んだ条件です。 find は存在しない値を探します。最初に見つかれば一操作ですが、最悪計算量の O(log n) は変わりません。
• O(1) は安い一操作とは限りません。 n を二倍にしても本例は 1 → 1 → 1 です。一回が高価でも、回数が増えなければ定数です。
• 個別の測定は縦軸が異なります。 O(1) は狭い範囲、O(n²) は高い範囲を使います。競走だけは固定の共通尺度で、(16, 256) が枠の上へ出ます。これは意図した表示です。高さを固定したグラフに、増え続ける二次関数は収まりません。
• 入力は 4 → 8 → 16 に固定。 ×1、+1、×2、×4 を比べるため、自由なスライダーはありません。

よくある間違い

• 「O(1) なら速い」。 定数という意味です。遅い一操作でも n に依存しなければ O(1)、速い全走査でも O(n) です。
• 2n + 3 と n を別の分類にする。 定数は傾きや位置を変えても線形という増加を変えません。
• n² を二回の走査と考える。 独立した二走査は 2n で O(n) です。外側の各回で内側を全部走査すると、本例の n² になります。
• 全ての低レベル命令を数える。 本例の関数では主要操作を数えられます。固定の付随作業は次数を変えません。
• 増加率を実時間と混同する。 競走は同じ操作間隔を使いますが、実際の時間は一操作の費用や入力規模にも依存します。

このレッスンでの簡略化

カウンターは主要操作だけを数え、ループの管理、比較、最後の表示などを個別には数えません。実際の時間はキャッシュやインタープリターにも影響され、小さな入力では曲線とずれることがあります。共通の計数モデルによって、これらの関数の入力増加に対する仕事量を示します。