16　計算量とBig-O記法

1. 計算量とは

計算量（time complexity）とは、アルゴリズムがデータ量に対してどれだけの処理時間を必要とするかを表す指標です。 「データ数 n が増えたとき、処理回数がどれくらい増えるか」を測ります。

2. Big-O記法（オーダー記法）

計算量は O(n) や O(log n) のように Big-O（ビッグ・オー）記法で表します。 これは「n が大きくなったときの増え方」だけに着目した表現です。

増え方のグラフ（イメージ）

3. Big-Oの考え方：3つのルール

ルール1：定数は無視する

処理が 3n + 5 回なら → O(n)
処理が 100n 回でも → O(n)

n がとても大きいとき、定数倍は無視できる。係数や定数項は捨てて、最も支配的な項だけを残す。

ルール2：最も大きい項だけを残す

n² + 3n + 5 → O(n²)
n + log n → O(n)

n が大きくなると n² の方が圧倒的に大きくなるので、他の項は無視。

ルール3：基本処理1回 = O(1)

代入、比較、四則演算など、データ量に関係なく一定時間で終わるものは O(1)。

4. コードから計算量を求める

パターン①：単純なループ → O(n)

for ( i を 0 から n - 1 まで 1 ずつ増やす )
    A[i] を出力      // O(1)
endfor
// 全体：n 回ループ × O(1) = O(n)

パターン②：二重ループ → O(n²)

for ( i を 0 から n - 1 まで 1 ずつ増やす )
    for ( j を 0 から n - 1 まで 1 ずつ増やす )
        // 何か処理       // O(1)
    endfor
endfor
// 全体：n × n × O(1) = O(n²)

パターン③：範囲が半分ずつ → O(log n)

while ( n が 1 より大きい )
    n ← n div 2       // 半分にする
endwhile
// n が半分になるたびに 1 ステップ → 約 log₂(n) 回で 1 に到達 → O(log n)

5. 主要アルゴリズムの計算量一覧

6. 空間計算量

時間ではなく使用するメモリ量に着目した指標を空間計算量といいます。 時間計算量と同じく Big-O 記法で表します。

7. 理解度チェック問題

問題16-1

次のコードの計算量はどれですか。

整数型: sum ← 0
for ( i を 1 から n まで 1 ずつ増やす )
    sum ← sum + i
endfor

問題16-2

次のコードの計算量はどれですか。

for ( i を 1 から n まで 1 ずつ増やす )
    for ( j を 1 から n まで 1 ずつ増やす )
        A[i] と A[j] を比較
    endfor
endfor

問題16-3

3n² + 100n + 500 の計算量を Big-O で表すとどれですか。

問題16-4

データ数 n=1,000,000 のとき、最も処理時間が短いのはどれですか。

問題16-5

n 個の要素がある配列から「目的の値」を探す。配列がソート済みのとき、最も効率的なアルゴリズムはどれですか。