Question

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

Answer 1

欧几里得算法求最大公约数方法如下：

欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。欧几里得算法在RSA加密算法中有运用。

算法分析：算法通过连续计算余数，知道余数是0为止，最后所得的非0余数就是最大公因数。例如 M=1989 ，N=1590，则余数序列为399，393，6，3，0。

因而，Gcd(1989,1590)=3，从余数的序列可知，这是一个快速收敛的算法。要想得出该算法的运行时间，就需要确定余数序列究竟有多长。

不妨大胆的猜测log(N)看似是非常理想的答案，但是余数序列递减的规律并非是按照常数因子所递减的，事实上，数学家们已经证明了，在两次迭代以后，余数的值最多是原始值的一半。由此可知，迭代次数之多是2log(N) = O(logN)从而得到算法的时间复杂度。下面，我们从数学家那里问来了证明过程。

时间复杂度证明定理：如果 M > N ，则 M mod N < M/2
证明：如果 N<=M/2 ，则余数小于N，故定理在这种情况下成立。如果 N>M/2 ，此时M仅含有一个N，从而余数为M-N。事实上，欧几里得算法的平均时间复杂度是需要大量的数学分析进行证明的，算法迭代的平均次数是（12ln2lnN）/pi^2+1.47。