辗转相除法 java 实现 及其时间复杂度证明

时间：2020-12-30 00:34:27

代码

    public static void main(String[] args) {
        Random r = new Random();
for (int ii = 0; ii < 10; ii++) {
int num1 = r.nextInt(100);
int num2 = r.nextInt(80);
            System.out.println(num1 + " " + num2 + " -> " + mod(num1, num2));
        }
    }
private static int mod(int a, int b) {
if (a < b)
return mod(b, a);

while (a % b != 0) {
int temp = b;
            b = a % b;
            a = temp; //这儿必须要有一个临时变量？
        }
return b;
    }

输出

66 26 -> 2
64 50 -> 2
19 61 -> 1
79 43 -> 1
81 1 -> 1
17 76 -> 1
74 66 -> 2
48 9 -> 3
1 70 -> 1
59 5 -> 1

证明

这儿我们用的是非递归实现。
简单证明一下。 设最大公约数为 m。则数 a=n1*m，b=n2*m。a-b=(n1-n2)*m，gcd(a,b)=gcd(b, a mod b)。也就是说 a 、b 的公约数和b、a%b 的公约数是一样的。

时间复杂度证明 ##

时间复杂度 log(n)，其中 n 为 a、b 间较大的数。

做一个实验：在10000以内两两辗转相除法，运算次数最多的是哪两个数呢？
6765和 4181
如果把上界再缩小或扩大，你会发现，出现的数都是斐波那契数列中的数，都是相邻的两项。
因为斐波那契数列相邻两项在做gcd的时候，每次mod只相当于做了一次a-b，退化成更相减损术了，而没有起到mod的加速效果。
而斐波那契数列有通项公式，Fn=(1.618)n/sqrt(5)，第n项的值是与某两个无理数的n次相关的。所以，是logn了

还有一种解答,数学证明很麻烦

我们先不考虑模运算本身的时间复杂度(算术运算的时间复杂度在Knuth的TAOCP中有详细的讨论), 我们只考虑这样的问题: 欧几里得算法在最坏情况下所需的模运算次数和输入的a和b的大小有怎样的关系?
我们不妨设a>b>=1(若a < b我们只需多做一次模运算, 若b=0或a=b模运算的次数分别为0和1), 构造数列{un}: u0=a, u1=b, uk=uk-2 mod uk-1(k>=2), 显然, 若算法需要n次模运算, 则有un=gcd(a, b), un+1=0. 我们比较数列{un}和菲波那契数列{Fn}, F0=1<=un, F1=1<=un-1, 又因为由uk mod uk+1=uk+2, 可得uk>=uk+1+uk+2, 由数学归纳法容易得到uk>=Fn-k, 于是得到a=u0>=Fn, b=u0>=Fn-1. 也就是说如果欧几里得算法需要做n次模运算, 则b必定不小于Fn-1. 换句话说, 若 b < Fn-1, 则算法所需模运算的次数必定小于n. 根据菲波那契数列的性质, 有Fn-1>(1.618)n/sqrt(5), 即b>(1.618)n/sqrt(5), 所以模运算的次数为O(lgb).

参考文章

http://www.aliog.com/67694.html

http://blog.csdn.net/u014285517/article/details/45392407

https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97
标签：

相关文章