§D2.8アルゴリズムの正当性と計算量

証明. まず、ループ入口に到達したすべての$k$について$P(\sigma_k)$が成り立つことを$k$に関する数学的帰納法（§A3.10 定理 1.1）で示す。

• 基底（$k=0$）。初期化条件より$P(\sigma_0)$。
• 帰納段階。$P(\sigma_k)$を仮定する。ループが入口$\sigma_{k+1}$に到達したということは、$\sigma_k$で継続条件$B(\sigma_k)$が真であり本体$S$が実行されたということである。維持条件より、その実行後の状態で$P(\sigma_{k+1})$が成り立つ。

よってループ入口に現れる各状態で$P$が成り立つ。いま仮定によりループは有限回$N$で停止する。停止するとは、状態$\sigma_N$に到達したとき継続条件が偽、すなわち$\lnot B(\sigma_N)$になることである。$\sigma_N$もループ入口の状態だから上で示したことより$P(\sigma_N)$が成り立ち、あわせて$P(\sigma_N) \land \lnot B(\sigma_N)$を得る。仮定した含意にこれを適用して$Q(\sigma_N)$が従う。▨

証明. 背理法による。ループが停止しないと仮定すると、ループ入口の状態の無限列$\sigma_0, \sigma_1, \sigma_2, \dots$が生じ、各段で継続条件が真だから、仮定により

という非負整数の無限狭義減少列が得られる。ところが集合$\{\, V(\sigma_k) : k \ge 0 \,\} \subseteq \mathbb{N}$は空でないから、$\mathbb{N}$の整列性（§A3.10 定理 2.1）により最小元をもつ。その最小元を$V(\sigma_m)$とすると、次の項$V(\sigma_{m+1}) < V(\sigma_m)$が同じ集合に属するのに最小元より小さく、最小性に反する。よって仮定は誤りで、ループは停止する。▨

証明. 不変条件として$P:\ \gcd(a, b) = \gcd(a_0, b_0)$をとる。まず補題として、$b > 0$のとき$\gcd(a, b) = \gcd(b,\ a \bmod b)$を示す。$r = a \bmod b$とおくと、ある整数$q$で$a = qb + r$と書ける。整数$d$が$a$と$b$の公約数ならば$d \mid (a - qb) = r$だから$d$は$b$と$r$の公約数であり、逆に$d$が$b$と$r$の公約数ならば$d \mid (qb + r) = a$だから$d$は$a$と$b$の公約数である。ゆえに$\{a, b\}$の公約数の集合と$\{b, r\}$の公約数の集合は一致し、その最大値も等しい。

この補題により不変条件を検証する。初期化では$\gcd(a, b) = \gcd(a_0, b_0)$が定義そのものから成り立つ。維持では、本体が実行されるのは$b \ne 0$（すなわち$b > 0$）のときで、更新後の対は$(b,\ a \bmod b)$だから補題より$\gcd(b,\ a \bmod b) = \gcd(a, b)$となり、不変条件が保たれる。

停止性は変量$V = b$（第二成分、非負整数）で示す。$b > 0$で本体を実行すると新しい第二成分は$a \bmod b < b$だから$V$は狭義に減少する。命題 1.4よりループは停止する。

終了では、停止時に継続条件の否定$b = 0$が成り立つ。不変条件とあわせて$\gcd(a, 0) = \gcd(a_0, b_0)$を得るが、$a > 0$の任意の約数が$0$を割るので$\gcd(a, 0) = a$、ゆえに返り値$a$は$\gcd(a_0, b_0)$に等しい。定理 1.2により手続きは正しい。▨

証明. 1. 仮定より$c_1 > 0,\ n_1$で$n \ge n_1$のとき$f(n) \le c_1 g(n)$、また$c_2 > 0,\ n_2$で$n \ge n_2$のとき$g(n) \le c_2 h(n)$。$n_0 = \max\{n_1, n_2\}$、$c = c_1 c_2$とおけば、$n \ge n_0$で$f(n) \le c_1 g(n) \le c_1 c_2 h(n) = c\,h(n)$。ゆえに$f = O(h)$。

2. 仮定より$n \ge n_1$で$f_1(n) \le c_1 g(n)$、$n \ge n_2$で$f_2(n) \le c_2 h(n)$。$n_0 = \max\{n_1, n_2\}$とすると、$n \ge n_0$で

定数$c_1 + c_2$をとれば$f_1 + f_2 = O(\max\{g, h\})$。

3. 比$a_n = n^k / b^n \ge 0$の挙動を調べる。$n \ge 1$で

$n \to \infty$で$(1 + 1/n)^k \to 1$だから、右辺は$1/b$に収束する。$1/b < 1$なので、$1/b < r < 1$をみたす定数$r$を一つ選ぶと、収束の定義よりある$N$が存在して、すべての$n \ge N$で$a_{n+1}/a_n \le r$となる。したがって$m \ge 0$について$a_{N+m} \le r^m a_N$が帰納的に従い、$0 \le r < 1$より$a_{N+m} \to 0$。ゆえに数列$(a_n)$は収束（$\to 0$）ゆえ有界で、ある$M$で$a_n \le M$が$n \ge N$で成り立つ。これは$n^k \le M b^n$（$n \ge N$）を意味し$n^k = O(b^n)$。

逆に$b^n = O(n^k)$と仮定すると、ある$c, n_0$で$n \ge n_0$のとき$b^n \le c\,n^k$、すなわち$a_n = n^k/b^n \ge 1/c > 0$となり、$a_n \to 0$に矛盾する。ゆえに$b^n \ne O(n^k)$。▨

証明.$n = b^k$とすると$k = \log_b n$。漸化式を$k$回展開すると、$T(1)$の係数は$a^k$、第$j$段（$j = 0, 1, \dots, k-1$）で統合コスト$f(n/b^j)$が$a^j$個生じるので

ここで$a^k = a^{\log_b n} = n^{\log_b a} = n^p$に注意する。右辺第一項は$\Theta(n^p)$である。第二項を$g(n) = \sum_{j=0}^{k-1} a^j f(n/b^j)$とおき、場合ごとに評価する。$f \ge 0$なので$T(n) \ge a^k T(1) = \Omega(n^p)$が常に成り立つことも用いる。

以下の各場合で、そこで用いる漸近評価がすべての$b^q\ge b^{q_0}$で成り立つように$q_0\ge 1$を固定する。$k\ge q_0$と$J=k-q_0$に対し、$g(n)$を$0\le j\le J$の段の和$g_{\mathrm{up}}(n)$と$J<j<k$の段の和$g_{\mathrm{low}}(n)$に分ける。後者では$r=k-j$と変数変換すると

となる。最後の和は$n$に依らない有限和であり、$q_0=1$の場合は空和とする。これが、漸近評価を直接適用できない再帰木下端の有限段の寄与である。

場合 1.$f(n) \le C\,n^{\,p-\varepsilon}$（$n\ge b^{q_0}$）とすると、$b^{\,p} = a$より$a / b^{\,p-\varepsilon} = b^{\varepsilon}$であって、$0\le j\le J$では

$b^\varepsilon > 1$の等比和で抑えると

$b^{\varepsilon k} = (b^k)^{\varepsilon} = n^{\varepsilon}$だから$g_{\mathrm{up}}(n)=O(n^p)$である。さらに$g_{\mathrm{low}}(n)=O(n^p)$なので$g(n)=O(n^p)$となり、第一項とあわせ$T(n) = \Theta(n^p)$を得る。

場合 2.$f(n) = \Theta(n^p)$のとき、$a / b^{\,p} = 1$より$0\le j\le J$の各段は、一様な定数で

となる。この範囲の段数は$J+1=k-q_0+1=\Theta(k)$だから$g_{\mathrm{up}}(n)=\Theta(kn^p)$である。$g_{\mathrm{low}}(n)=O(n^p)$かつ$k=\Theta(\log n)$なので、$g(n)=\Theta(n^p\log n)$となる。第一項$\Theta(n^p)$はこれに吸収され$T(n)=\Theta(n^p\log n)$を得る。

場合 3.$f(n)=\Omega(n^{p+\varepsilon})$の評価と正則条件がともに$n\ge b^{q_0}$で成り立つように$q_0$を選ぶ。$0\le j\le J$では、正則条件を$j$回反復適用して$a^j f(n/b^j) \le c^j f(n)$を得る。したがって

また$g_{\mathrm{low}}(n)=O(n^p)=O(f(n))$であるから$g(n)=O(f(n))$であり、$j=0$の項から$g(n)\ge f(n)$なので$g(n)=\Theta(f(n))$となる。さらに$n^p=O(f(n))$だから第一項も吸収され、$T(n)=\Theta(f(n))$を得る。▨

証明.§D2.9 定義 4.1では、比較だけで入力の順序を識別する計算モデルを定めています。そのモデルに対して§D2.9 系 4.6では、相異なる$n$個の要素を正しく整列する決定木の高さが$\log_2(n!)=\Omega(n\log n)$以上であることを証明しています。決定木の高さは最悪の場合の比較回数に等しいので、本命題が従います。▨