アルゴリズム論特論（塩田）第4回 (2)
ユークリッドのアルゴリズムの計算量（ 詳細な評価 ）
詳細な評価
Th.5 ( 詳細な評価 ) ユークリッドのアルゴリズムの計算量は $O(\log^2 a)$.
その証明の前に、除算の計算量を詳しく見ておきましょう。
Lemma 6 除算 $x \div y$ の計算量は、商を $q$ として $O(\log y \times \log q)$.
第1回の講義では大雑把に $O(\log^2 x)$ と言っていましたが、もう少し小さい、ということになります。
証明
筆算の各段は除数 $y$ の桁数の引き算で、
それを高々 ( 商 $q$ のビット長 ) 回繰り返します。
従ってその計算量は
$O$( $y$ のビット長 ) $\times$ $O$( $q$ のビット長 ) = $O(\log y) \times O(\log q) = O(\log y \times \log q)$.
(証明終)
Th.5 の証明
$r_n$ を $r_{n+1}$ で割った商を $q_n = \lfloor r_n / r_{n+1}\rfloor$ とおきます。全ての番号 $n$ で
$r_{n+2} = r_n - q_n \times r_{n+1}$
であり、特に終了時の番号 $N$ では
$0 = r_{N+1} = r_{N-1} - q_{N-1} \times r_{N}$
となっています。$n \geqq 1$ のときは
$r_n \leqq r_1 = b \lt a$
ですから
$r_n \div r_{n+1}$ の計算量 $= O(\log r_{n+1}) \times O(\log q_n) = O(\log a) \times O(\log q_n)$
アルゴリズム全体でこれを加えると
\begin{align}
\sum_{n=0}^{N-1} O(\log a) \times O(\log q_n) &= O(\log a) \times \sum_{n=0}^{N-1} O(\log q_n) \\
&= O(\log a) \times O\left(\sum_{n=0}^{N-1} \log q_n\right) \\
&= O(\log a) \times O(\log (q_0 \times \cdots \times q_{N-1})) \quad \cdots\cdots\ (\ast)\\
\end{align}
ここで、全ての番号 $n$ で
$r_n = q_n \times r_{n+1} + r_{n+2} \geqq q_n \times r_{n+1}$
が成り立ちますので
\begin{align}
a = r_0 &\geqq q_0 \times r_1 \\
&\geqq q_0 \times q_1 \times r_2 \\
&\ \ \vdots \\
&\geqq (q_0 \times \cdots \times q_{N-1}) \times r_N \\
&\geqq (q_0 \times \cdots \times q_{N-1}) \\
\end{align}
よって
$(\ast)$ の右辺 $ = O(\log a) \times O(\log a) = O(\log^2 a)$.
(証明終)