2.4.7 性能不明显的计算
在很多情况下，仅仅通过算法的描述（如加法和乘法）就可以分辨出算法的性能是线性级还是平方级的。例如，平方级的主要特征是嵌入的循环结构。但是，这样的直接分析对某些算法却无法使用。例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)) {
// 最后一个参数表示结果符号，这里可以忽略它，
// 因为我们总是用大数减去小数
// 注意如果a > b，compareTo(a, b)的结果为正数if (compareTo (a, b) > 0) {
subtract (a, b, gcd, new int[1]);
assign (a, gcd);} else{
subtract (b, a, gcd, new int[1]);
assign (b, gcd);
}}
// a的值就是原先a和b的最大公约数
assign (gcd, a);
}
这个算法不断地比较a和b，然后用大数减去小数直至得到0为止。其中的辅助函数（isZero、assign、compareTo和subtract）都可以在代码库中找到。
虽然这个算法可以计算出两个数的最大公约数，但是对于给定的输入规模，要经过多少次迭代，这个答案并不明显。由于每一次循环之后，a或者b都不会变为负数，因此能够保证的是这个算法一定会结束，但是某些GCD的计算可能会需要较长的时间，例如，该算法计算gcd(1000, 1)时会执行999步！很明显，这个算法的性能对于输入数据的敏感程度比乘法和加法算法要大得多。对于相同规模的输入来说，GCD算法的时间是随着输入数据的变化而变化的。GCD算法在计算(10k－1, 1) 的最大公约数时性能最差，它需要处理n＝10k－1次循环！由于加法和减法在数据规模为n时的时间复杂度均为O(n)，因此GCD算法可以被归类为O(n2)。
例2-6中ModGCD算法的性能要比例2-5的GCD实现好得多，这个算法使用取模计算a除以b的余数。
例2-6：ModGCD 算法计算最大公约数
public static void modgcd (int a[], int b[], int gcd[]) {
if (isZero(a)) { assign (gcd, a); return; }
if (isZero(b)) { assign (gcd, b); return; }
// 将a、b调整到相同位数，然后在其副本上进行计算
a = copy(normalize(a, b.length));
b = copy(normalize(b, a.length));
// 确保a比b大，同时返回最大公约数
int rc = compareTo(a,b);
if (rc == 0) { assign (gcd, a); return; }
if(rc < 0){
int t[]=b;
b=a;
a=t; }
int quot[] = new int[a.length];
int remainder[] = new int[a.length];
while (!isZero(b)) {
int t[] = copy (b);
divide (a, b, quot, remainder);
assign (b, remainder);
assign (a, t);
}
// a 的值就是原始的（a，b）的最大公约数
assign (gcd, a);
}
ModGCD能够更快地得到解，因为它不会在while循环中不断地从大数中减去小数。这个差异并不仅仅体现在实现细节上，也反映了在如何使用算法解决问题方面的一个根本性改变。
图2-5和表2-5展示了针对随机产生的142个n位数，求解所有10 011对整数对最大公约数的计算结果。 
图2-5：比较gcd和modgcd算法
对于随机数据，即便ModGCD实现比对应的GCD实现约快3倍，它的性能依旧是平方级，也就是O(n2)。分析ModGCD算法的最坏情况有些难度，研究表明当ModGCD处理两个连续的Fibonacci数字时性能最差。从图2-5上也可以推断出算法是平方级的，因为算法性能在数据规模翻倍后变为原先的4倍。
计算最大公约数还有着更为优秀的算法，不过这些算法主要针对特别大的整数，因而在实际场景中并不实用。
