正当性 (correctness) と停止性 (termination)の違いについて

正しいアルゴリズムとは何か

アルゴリズムを評価するとき、速度も重要ですが、まず次の 2 点を確認しましょう。

• 正当性 (correctness): 入力の前提条件を満たすとき、期待どおりの出力を返すこと
• 停止性 (termination): 有限回の手順で処理が終わること

どちらが欠けてもアルゴリズムとしては成立しません。たとえば「1 秒で答えが返るが、そのうち 3 割は間違っている」処理は使えませんし、「答えが合っているはずでも永遠に終わらない」処理も実用になりません。

正当性の考え方

正当性を示すとは、「この手順で目的の答えが得られる」ことを論理的に確かめることです。「たぶん合っていそう」という感覚では裏づけになりません。

例として、配列の最大値を求める次のアルゴリズムを見ます。

Algorithm MaxValue(A)
    max_value ← A[0]
    for i ← 1 to length(A) - 1
        if A[i] > max_value
            max_value ← A[i]
    return max_value

このアルゴリズムが正しいのは、ループの各反復が終わった時点で「max_value は A[0] から A[i] までの最大値になっている」という性質が保たれているからです。たとえば A = [3, 1, 4, 1, 5] で追ってみると次のようになります。

各行で「ここまでに見た要素の最大値」が max_value に入っています。ループを抜けた時点では配列全体を見終わっているので、max_value が配列全体の最大値になります。

このように、ループの反復で成り立ち続ける性質のことを ループ不変式 (loop invariant) と呼びます。ループ不変式は動的計画法やグラフ探索など、後で出てくる多くのアルゴリズムで繰り返し使う基本道具です。

停止性の考え方

停止性は、「この手順がいつか終わるか」を確認することです。とくにループや再帰を使うアルゴリズムでは必ず意識する必要があります。

先ほどの MaxValue は、for i ← 1 to length(A) - 1 という形の反復なので、配列の長さを n とするとループは n - 1 回で終わります。つまり停止します。

一方で、次のコードは停止しません。

while x ≠ 0
    x ← x + 1

たとえば x = 3 から始めると、x は 4, 5, 6, ... と増え続けるだけで 0 になりません。停止性を調べるときの基本は、「毎回の反復で終了条件に近づいているか」を見ることです。上の例では終了条件（x = 0）から遠ざかっているので、停止しないと判断できます。

部分正当性と完全正当性

ここまで、正当性（答えが正しいこと）と停止性（有限回で終わること）を別の論点として扱ってきました。この 2 つの関係を整理するために、次の用語が使われることがあります。

• 部分正当性 (partial correctness): 停止したなら、その答えは正しい
• 完全正当性 (total correctness): 停止し、かつ答えも正しい

言い換えると、完全正当性は「部分正当性 + 停止性」です。たとえば先ほどの MaxValue は、ループ不変式から「停止すれば最大値を返す」が言えて、さらに反復回数が有限なので停止もする、という 2 段構成で完全正当性が示せます。

正当性と停止性を示す方法

正当性側

1. ループ不変式を使う

前節で使った方法です。ループの各反復の前後で成り立つ性質を見つけ、ループ終了時にその性質から目的の結論が導けることを示します。if 文などで処理が分岐する場合は、各分岐ごとに不変式が保たれることを確認します（たとえば MaxValue なら「A[i] > max_value なら更新する／しない」の 2 つの枝それぞれで、不変式「max_value はここまでの最大値」が崩れないことを見ます）。主に反復型のアルゴリズムに向きます。

2. 数学的帰納法を使う

再帰アルゴリズムや、入力サイズが小さくなっていくアルゴリズムで使います。「サイズが n 未満のすべての入力で正しく動く」と仮定して、サイズ n でも正しく動くことを示す流れです（強い帰納法）。数学で使う帰納法と同じ構造で、再帰呼び出しの戻り値が正しいと仮定して元の呼び出しの正しさを導く、という形になります。

停止性側

3. 反復ごとに減っていく量に注目する

残りの処理対象数、探索範囲の幅、再帰の深さなど、「毎回減っていく非負整数」を見つけられれば、その値は有限回で 0 に到達するので処理は終わります。MaxValue なら「残りの i の個数」、Factorial(n) なら「引数 n の値」が変量になります。

例: 線形探索で正しさと停止を考える

配列 A の中に値 x があるかを調べる線形探索で、正当性と停止性を実際に確認します。

Algorithm LinearSearch(A, x)
    for i ← 0 to length(A) - 1
        if A[i] = x
            return true
    return false

• 正当性: 先頭から順に全要素を調べ、途中で x と一致するものが見つかれば true を返す。最後まで見つからなければ配列内に x は存在しないので false を返す。よって返り値は「x が配列内にあるか」と一致する
• 停止性: for ループの回数は最大でも配列の長さ length(A) 回。途中で一致が見つかれば、そこで return して早く終わる

このように、正当性では「返り値が問題の答えと対応しているか」を、停止性では「ループ回数が有限か、または終了条件に到達するか」を見ます。

確認チェック

アルゴリズムを書いたあと、次の点を自分で確認すると精度が上がります。

• 入力の前提条件は明確か（空配列は許すか、負の数は来るか など）
• すべての分岐で返り値または次の処理が決まっているか
• ループが終わる理由を言葉で説明できるか
• 再帰が止まる条件を言葉で説明できるか
• 小さな具体例（要素数 0, 1, 2 程度）で手で追っても期待どおりに動くか

「コードを動かしたら通った」は正しさの根拠としては弱めです。たまたま試したケースで動いても、空配列や重複要素、境界値などで壊れることはよくあります。だからこそ、正当性と停止性は実行ではなく論理で確認する価値があります。

まとめ

アルゴリズムの品質を考えるとき、正当性と停止性は最初の関門です。

• 正当性: 答えと一致するか
• 停止性: 有限回の手順で処理が終わるか

速度の議論は、この 2 つを満たしたうえで初めて意味を持ちます。これから新しいアルゴリズムを学ぶときも、まず「なぜ正しいのか」「なぜ止まるのか」を自分の言葉で言い直してみると理解が深まります。とくにループ不変式（反復で保たれる性質）と、減っていく変量（止まる理由）を意識できるようになると、多くのアルゴリズムの解説が読みやすくなります。