アルゴリズムクイックリファレンス 第2版

30

■

2

章 アルゴリズムの数学

2.4.7

 あまり明白でない性能を示す計算

ほとんどの場合は、（

加算アルゴリズム

や

乗算アルゴリズム

で示したように）線形か

二乗かの分類で、アルゴリズムの記述は十分だ。二乗の計算になる徴候の第一は、

入れ子になったループ構造があることだ。しかし、アルゴリズムによっては、この

ような単純な分析で手に負えないものがある。ユークリッドが考案した

2

つの整数

の最大公約数を計算する例2-5の最大公約数（

GCD

）アルゴリズムを考えてみよう。

例

2-5

 ユークリッドの

GCD

アルゴリズム

public static void gcd(int a[], int b[], int gcd[]) {

if (isZero(a)) { assign(gcd, a); return; }

if (isZero(b)) { assign(gcd, b); return; }

a = copy(a); // a

と

b

が途中で変更されないようにコピーしておく

b = copy(b);

while (!isZero(b)) {

// subtract

の最後の引数は結果の符号を表す。今回行うのは、

//

大きい数から小さい数を引く操作だけなので、無視できる。

// a > b

なら

compareTo(a, b)

が正であることに注意。

if (compareTo(a, b) > 0) {

subtract(a, b, gcd, new int[1]);

assign(a, gcd);

} else ...