時間計算量 — Project Hematite

漸近的記法が言語を与えてくれた。時間計算量はそれを実際のコードに適用するものだ。このチェックポイントでは、アルゴリズムが実行する操作を数える方法、その数を支配的な項に削減する方法、そして一般的な制御フローパターンから直接結果を読み取る方法を示す — コードを実行することなくどんなアルゴリズムのコストも分類できるようになる。

何を数えるか

時間計算量（time complexity）は入力のサイズを算術演算などの基本操作（elementary operation）の数にマッピングする関数 $T(n)$ だ。基本操作とは定数時間で実行できるもの：2 数の比較、加算、メモリアドレスへの書き込み、参照を辿るなど。これらをすべてコスト 1 単位として数える。

「入力サイズ」の定義は問題による：

リストや配列の場合： $n$ は要素数。
数の場合： $n$ はビット数（または桁数）であって値そのものではない。1000 桁の数が偶数かどうかを計算するのは、その値まで繰り返すより遥かに少ない仕事だ。
グラフの場合：通常 $n$ を頂点数、 $m$ を辺数として両方で計算量を表現する。

最悪ケース、最良ケース、平均ケース

同じアルゴリズムでも同じサイズの異なる入力に対して振る舞いが大きく異なることがある。 $n$ 要素の未ソート配列からターゲット値を探すことを考えよう：

最良ケース：ターゲットが最初の要素 — 1 回の比較で十分。
最悪ケース：ターゲットが最後の要素か、存在しない — $n$ 要素すべてをチェックする。
平均ケース：ターゲットが一様ランダムに現れると仮定すると、平均で約 $n/2$ 要素をチェックする。

特に断りがない限り、このシリーズの時間計算量は最悪ケースの時間計算量を意味する。最悪ケース分析は保証を与える：サイズ $n$ のどんな入力を与えても、アルゴリズムは $T(n)$ ステップ以上かからない。

最良ケース分析はほとんど役に立たない — 物事がうまくいくことを知っても、うまくいかないときに保護してくれない。平均ケース分析は価値があるが、常に正当化されるとは限らない入力分布に関する仮定が必要だ。重要な場面で導入する。

コードから時間計算量を読む

最も重要な実践的スキルは制御フローを計算量の式に変換することだ。以下のパターンが遭遇するケースの大部分をカバーする。

単純な文

固定量の仕事をする単一の文 — 比較、代入、算術演算 — は $n$ に関わらず $O(1)$ を全体に貢献する。

let mid = lo + (hi - lo) / 2;  // O(1)

単純なループ

$n$ 回実行し、1 回の反復で $O(1)$ の仕事をするループは合計 $O(n)$ だ。

fn sum(arr: &[i64]) -> i64 {
    let mut total = 0;
    for &x in arr {   // n 回の反復、各反復 O(1) の仕事
        total += x;
    }
    total
}

ネストしたループ

内側のループが外側ループの $n$ 回各反復に対して最大 $n$ 回実行される 2 つのループは $O(n) \times O(n) = O(n^2)$ だ。

fn has_duplicate(arr: &[i64]) -> bool {
    for i in 0..arr.len() {             // n 回の反復
        for j in (i + 1)..arr.len() {  // 最大 n 回の反復
            if arr[i] == arr[j] {
                return true;
            }
        }
    }
    false
}

内側のループは外側の反復 $i = 0, 1, \ldots, n-1$ に対して $n-1, n-2, \ldots, 1, 0$ ステップ実行され、合計 $\frac{n(n-1)}{2}$ 回の比較になる。これは $\Theta(n^2)$ だ。

半分にするループ

ループ変数が 1 ずつ増えるのではなく毎回定数で割られる（または掛けられる）とき、ループは $O(\log n)$ 回実行される。

fn floor_log2(mut n: u64) -> u64 {
    let mut count = 0;
    while n > 1 {
        n /= 2;       // n が毎回半分になる
        count += 1;
    }
    count
}

$n$ から始まって 1 になるまで半分にするには $\lfloor \log_2 n \rfloor$ ステップかかる。二分探索も同じ議論が成り立つ：各ステップで探索空間が半分になるのでステップ数は $O(\log n)$ だ。

逐次ブロック

独立したコードブロックが次々に実行される場合、それらの計算量を加算し、支配的な項だけを残す：

O(n^2) + O(n) = O(n^2).

// ブロック 1：O(n)
let total: i64 = arr.iter().sum();

// ブロック 2：O(n^2) — こちらが支配する
for i in 0..arr.len() {
    for j in (i + 1)..arr.len() {
        // ペア (i, j) を処理
    }
}

全体は $O(n^2)$ だ。

非一様な上限を持つネストループ

すべてのネストループが $O(n^2)$ になるわけではない。内側の上限が外側の変数に依存する場合、和を明示的に計算しなければならない。

for i in 0..n {
    for j in 0..i {  // 内側は n ステップではなく i ステップ実行される
        // O(1) の仕事
    }
}

総反復数： $0 + 1 + 2 + \cdots + (n - 1) = \frac{n(n-1)}{2} = \Theta(n^2)$ 。この場合も二乗だが、パターンが重要だ — 他の非一様な上限では異なる和になる。

例えば for j in 0..(2*i) の形なら $\sum_{i=0}^{n-1} 2i = n(n-1) = \Theta(n^2)$ だが、for j in 0..((i as f64).sqrt() as usize) なら $\sum_{i=0}^{n-1} \sqrt{i} = \Theta(n^{3/2})$ になる。

支配項の法則

最も重要な簡略化：最も速く増える項だけ残し、定数倍を除く。

$T(n) = 5n^3 + 100n^2 + 10^6 \cdot n + 10^9$ のとき $T(n) = \Theta(n^3)$ だ。

なぜか？大きな $n$ では $5n^3$ が他のすべての項を合わせたものより速く増える。 $n$ が十分大きくなると $5n^3$ が $T(n)$ の半分以上を占め、残りは無視できる。

より形式的に、 $g(n) = o(f(n))$ となる 2 つの増加クラスについて：

f(n) + g(n) = \Theta(f(n)).

系として：コードを解析するとき、「最内側」または「支配的な」ループを特定してそのコストを求めれば、それが全体の計算量になる。すべての定数を追跡する必要はない。

具体例：二分探索

二分探索はソート済み配列の中でターゲット値を、探索範囲を繰り返し半分にすることで見つける。

fn binary_search(arr: &[i64], target: i64) -> Option<usize> {
    let mut lo = 0;
    let mut hi = arr.len();

    while lo < hi {                          // (1)
        let mid = lo + (hi - lo) / 2;       // O(1)
        match arr[mid].cmp(&target) {
            std::cmp::Ordering::Equal => return Some(mid),
            std::cmp::Ordering::Less => lo = mid + 1,
            std::cmp::Ordering::Greater => hi = mid,
        }
    }
    None
}

while ループ (1) の各反復で探索範囲 $[lo, hi)$ が半分になる。サイズ $n$ から始まって、 $k$ 回の反復後には範囲のサイズが $\lceil n / 2^k \rceil$ になる。ループは範囲が空になったとき終了し、それは最大 $\lceil \log_2 n \rceil + 1$ 回の反復後だ。各反復は $O(1)$ の仕事をする。

合計： $O(\log n)$ 。

線形探索は $O(n)$ であることと比較しよう。 $n = 10^9$ のとき、線形探索は最大 $10^9$ 回の比較を行うが、二分探索は最大 30 回だ。

空間計算量についての注記

時間計算量は操作数を数える。空間計算量（space complexity）は $n$ の関数としてのメモリ使用量を同じ漸近的記法で数える。サイズ $n$ の補助配列を確保するアルゴリズムは $O(n)$ の余分な空間を使い、固定個数の変数しか使わないアルゴリズムは $O(1)$ の余分な空間を使う — これをインプレース（in-place）とも呼ぶ。

アルゴリズム解析では 2 つの指標は常に一緒に登場する。実行時間計算量が許容範囲でも $O(n^2)$ のメモリを必要とする高速なアルゴリズムは実用的でないことがある。

まとめ

時間計算量は漸近的記法で表した入力サイズ $n$ の関数としての基本操作数だ。
デフォルトでは最悪ケースの時間計算量を報告する — それが最も強力な有用な保証だ。
コードからの主なパターン：単純な文は $O(1)$ 、単純なループは $O(n)$ 、全範囲の 2 重ネストループは $O(n^2)$ 、半分にするループは $O(\log n)$ 、逐次独立ブロックは加算してから支配項を残す。
非一様な上限のネストループは $O(n^2)$ と仮定せず和を明示的に計算する。
支配項の法則：最も速く増える項だけ残し、定数倍を除く。
空間計算量は同じ記法でメモリ使用量を表す。インプレースは $O(1)$ の余分な空間を意味する。