Loading... # 辗转相除法 ## 原理 $$ gcd(a,b)=gcd(a\space mod\space b,a) $$ 为了使这个等式有计算意义,我们假定a > b。 ## 代码 ```java public static long divisionGcd(long m, long n) { while(n != 0) { long rem = m % n; m = n; n = rem; } return m; } ``` 这里我们不要求m ≥ n,因为如果m < n,一次迭代相当于m,n进行了一次交换。 ## 时间复杂度 这个算法的时间复杂度为O(logN),一个较粗略的证明方法是: **引理1**:如果一个算法能在O(1)时间内将问题的规模减小为原来的一半,则这个算法的时间复杂度是O(logN)。 **引理2**:若a, b > 0 $$ a\space mod\space b < \frac a2 $$ 证明:分情况讨论: 如果b < a/2,显然余数小于b,即小a/2。 如果b ≥ a/2,我们有a mod b = a mod (a - b),转化为第一种情况。 有以上两个引理,不难证明经过两次迭代,问题的规模最少减小一半,从而可以证明这个算法的时间复杂度上界是O(logN)。 最后修改:2020 年 04 月 22 日 © 允许规范转载 赞 0 如果觉得我的文章对你有用,请随意赞赏