面试中算法(最大公约数）

约定不等于承诺〃 2024-05-28 10:21 64阅读 0赞

### 高效求出两个整数的最大公约数，要尽量优化算法的性能。 ###

def getDiv(a,b):
        ma=max(a,b)
        mi=min(a,b)
        #判断能被整除
        if ma%mi==0:
            return mi
        #递归
        return getDiv(ma%mi,mi)
    
    if __name__ == '__main__':
        # print(getDiv(10, 25))
        print(getDiv(1000, 50))

没错，这确实是**辗转相除法**的思路。不过有一个问题，当两个整数较大时，做 a%b取模运算的性能会比较差。

> **更相减损术**，出自中国古代的《九章算术》，也是一种求最大公约数的算法。  
> 它的原理更加简单:两个正整数a和b (a>b)，它们的最大公约数等于a-b的差值c和较小数b的最大公约数。例如，10和25，25减10的差是15，那么10和25的最大公约数，等同于10和15的最大公约数。

def getDiv(a,b):
        #如果相等，就是最大公约数
        if a==b:
            return a
        #求出最大值，最小值
        ma=max(a,b)
        mi=min(a,b)
        #递归调用
        return getDiv(ma-mi,mi)
    
    
    if __name__ == '__main__':
        print(getDiv(100, 75))

更相减损术依靠两数求差的方式来递归，运算次数肯定远大于辗转相除法取模方式。如计算10000和1的最大公约数，就要递归9999次!

有什么办法可以既避免大整数取模，又能尽可能地减少运算次数呢?

> 最优方法:把**辗转相除法和更相减损术的优势结合起来**，在更相减损术的基础上使用移位运算。

当a和b均为偶数时，gcd (a，b) =2xgcd (a/2，b/2)=2xgcd (a>>1，b>>1)。

当a为偶数，b为奇数时，gcd (a，b) = gcd (a/2，b) = gcd (a>>1，b）。

当a为奇数，b为偶数时，gcd (a，b) = ged (a，b/2) = ged (a，b>>1)。

当a和b均为奇数时，先利用更相减损术运算一次，gcd (a，b) = gcd (b，a-b)，此时a-b必然是偶数，然后又可以继续进行移位运算。

> 其中：gcd是求最大公约数的方法，a是第一个数，b是第二个数。

![154b4848bd614217a037270049fe4c56.png][]![e014663891c849be87be5d0f3919904c.png][]

def getDiv3(a,b):
        #如果相等，就是最大公约数
        if a==b:
            return a
        #a,b都为偶数,，则a,b都右移1位，再乘以2
        if(a&1)==0 and (b&1)==0:
            return getDiv3(a>>1,b>>1) <<1
        # a为偶数，b为奇数，则a右移1位
        elif (a&1)==0 and (b&1)!=0:
            return getDiv3(a>>1,b)
        # a为奇数，b为偶数，则b右移1位
        elif (a&1)!=0 and (b&1)==0:
            return getDiv3(a,b>>1)
        else:
            #求出最大值，最小值
            ma=max(a,b)
            mi=min(a,b)
            #递归调用
            return getDiv3(ma-mi,mi)
    
    
    if __name__ == '__main__':
        print(getDiv3(10, 25))
        print(getDiv3(10000, 55))

> 总之：
> 
> 1.辗转相除法:时间复杂度不太好计算，可以近似为O(log (max (a，b)) )，但是取模运算性能较差。
> 
> 2.更相减损术:避免了取模运算，但是算法性能不稳定，最坏时间复杂度为O (max (a，b) ) 。
> 
> 3.更相减损术与移位相结合:不但避免了取模运算，而且算法性能稳定，时间复杂度为O(log (max (a，b) ) ) 。

[154b4848bd614217a037270049fe4c56.png]: https://img-blog.csdnimg.cn/direct/154b4848bd614217a037270049fe4c56.png
[e014663891c849be87be5d0f3919904c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/7a0caf3af7f54797ad1e9d79da00dde5.png