使用欧几里得算法求最大公约数

算法 everyinch 1189℃ 0评论

两个整数的最大公约数(greatest common divisor,GCD)是能被这两个整数整除的最大数。下面的程序给出了一个求两个整数m和n的最大公约数的穷举算法。穷举(brute force)法指使用最简单和直接,或者非常明显的方式解决问题的一种算法。结果是,为了解决一个给定问题,这样的算法相比更聪明或者更复杂的算法而言,可能导致做更多的工作。另外一方面,穷举算法相对于复杂的算法而言,通常更加易于实现,并且因为其简单性,有时候可以更加高效。

穷举算法检测k(k=2,3,4,…)是否是n1和n2的公约数,直到k大于n1或n2。该算法可以如下描述:

public static int gcd(int m, int n) {

int gcd = 1;

for (int k = 2; k <= m && k <= n; k++) {

if (m % k == 0 && n % k == 0)

gcd = k;

}

return gcd;

}

假设m>=n,那么,显然该算法的复杂度是O(n)

是否还有求最大公约数的更好的算法?不从1向上开始查找可能的除数,而是从n开始向下查找,这样会更高效。一旦找到一个除数,该除数就是最大公约数。因此,可以使用下面的循环来改进算法:

for(int k=n;k>=1;k–){

if(m%k==0 && n%k==0){

gcd=k;

break;

}

}

这个算法比前一个效率更高,但是它的最坏情况的时间复杂度依旧是O(n),数字n的除数不可能比n/2大。因此,可以使用下面的循环进一步改进算法:

for(int k=m/2;k>=1;k–)(

if(m%k==0 && n%k==0){

gcd=k;

break;

}

}

但是,该算法是不正确的,因为n可能会是m的除数。这种情况必须考虑到。

假设m>=n,那么这个for循环最多执行n/2次,比前一个算法节省了一半的运行时间,该算法的时间复杂度仍然是O(n),但实际上,它比上面的算法快得多。

注意:大O标记提供了对算法效率的一个很好的理论上的估算。但是,两个算法即使有相同的时间复杂度,它们的效率也不一定相同。如前面的例子所示,两个算法具有相同的复杂度,但实际上,后面的算法显然更好些。

求最大公约数的一个更有效的算法是在公元前300年左右由欧几里得发现的,这是最古老的著名算法之一。它可以递归地定义如下:

用gcd(m,n)表示整数m和n的最大公约数:

如果m%n为0,那么gcd(m,n)为n。

否则,gcd(m,n)就是gcd(n,m%n)o

不难证明这个算法的正确性。假设m%n=r,那么,m=qn+r,这里的q是m/n的商。能整除m和n的任意数字都必须也能整除r。因此,gcd(m,n)和gcd(n,r)是一样的,其中r=m%n。

最好的情况是当m%n为0的时候,算法只用一步就能找出最大公约数。分析平均情况是很困难的。然而,我们可以证明最坏情况的时间复杂度是O(logn)。

假设m>=n,我们可以证明m%n<m/2,如下所示:

如果n<=m/2那么m%n<m/2因为根除以n的余数总是小于n。

如果n>m/2那么m%n=m-n<m/2o因此,m%n<m/2。

欧几里得的算法递归地调用gcd方法。它首先调用gcd(m,n),接着调用gcd(n,m%n),然后是gcd(m%n,n%(m%n)),以此类推,如下所示:

gcd(m,n)

= gcd(n,m%n)

= gcd(m%n,n%(m%n))

=…

因为m%n<m/2且n%(m%n)<n/2,所以传递给gcd方法的参数在每两次迭代之后减少一半。在调用gcd两次之后,第二个参数小于n/2。在调用gcd四次之后,第二个参数小于n/4。在调用gcd六次之后,第二个参数小于n/23o假设k是调用gcd方法的次数。在调用gcd方法k次之后,第二个参数小于n/2(k/2),它是大于或等于1的。也就是

因此,k<=2logn。所以该gcd方法的时间复杂度是O(logn)。

最坏情况发生在两个数导致了最大分离的时候。事实证明,两个连续的斐波那契数会造成最大分离的情况。回顾斐波那契数列是从0和1开始,然后后一个数都是前两个数的和,例如:

0 1 1 2 3 5 8 13 21 34 55 89…

这个数列可以递归地定义为

fib(0)=0;

fib(1)=1;

fib(index)=fib(index-2)+fib(index-1);index>=2

对于两个连续的斐波那契数fib(index)和fib(index-1),

gcd(fib(index), fib(index − 1))

= gcd(fib(index − 1), fib(index − 2))

= gcd(fib(index − 2), fib(index − 3))

= gcd(fib(index − 3), fib(index − 4))

= . . .

= gcd(fib(2), fib(1))

= 1

因此,gcd方法被调用的次数和下标相等。我们可以证明index<=1.441ogn,其中n=fib(index-1)。这是一个比index<=2logn更严格的限定。

分享&收藏

转载请注明:陈童的博客 » 使用欧几里得算法求最大公约数

喜欢 (4)
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
'; } if( dopt('d_footcode_b') ) echo dopt('d_footcode'); ?>