欧几里得算法(Euclidean Algorithm)的迭代次数和算法复杂度的证明

我们直到欧几里得算法是计算两个数的最大公因数（或者两个多项式的最大公因式），并且在其他算法中（例如因子分解算法）经常会用到欧几里得算法。本篇专门证明欧几里得算法的迭代次数和计算复杂度。

欧几里得算法描述

设我们研究的问题是利用欧几里得算法求gcd(a,b)gcd(a,b)gcd(a,b)，求解算法流程如下：

Euclidean Algorithm(a,b)

r0=a,r1=b,m=1r_{0}=a,r_{1}=b,m=1r0​=a,r1​=b,m=1

while rm≠0r_{m} \ne 0rm​​=0

​ qm=⌊rm−1rm⌋q_{m}=\lfloor \frac{r_{m-1}}{r_{m}}\rfloorqm​=⌊rm​rm−1​​⌋

rm+1=rm−1−qmrmr_{m+1}=r_{m-1}-q_{m}r_{m}rm+1​=rm−1​−qm​rm​

​ m=m+1m=m+1m=m+1

return rm−1=gcd(a,b)r_{m-1}=gcd(a,b)rm−1​=gcd(a,b)

我们先给出结论：

欧几里得算法的迭代次数是n=O(min{log⁡2a,log⁡2b})n=O(min\lbrace \log_{2}a,\log_{2}b\rbrace)n=O(min{log2​a,log2​b})。欧几里得算法的单位乘法次数是n2n^{2}n2（有很多资料粗略的写成n3n^{3}n3）。

为了更容易叙述证明过程，我把Euclidean算法的过程写成迭代方程的形式：

r0=ar1=br0=q1r1+r2r1=q2r2+r3⋮rm−1=qmrm+rm+1r_{0}=a\\ r_{1}=b\\ r_{0}=q_{1}r_{1}+r_{2}\\ r_{1}=q_{2}r_{2}+r_{3}\\ \vdots\\ r_{m-1}=q_{m}r_{m}+r_{m+1} r0​=ar1​=br0​=q1​r1​+r2​r1​=q2​r2​+r3​⋮rm−1​=qm​rm​+rm+1​

并且迭代结束时rm+1=0r_{m+1}=0rm+1​=0。

证明：为了方便叙述，不妨令a>ba>ba>b。

先证明一个结论：对∀0≤i≤m−2\forall 0\le i\le m-2∀0≤i≤m−2，有ri≥2ri+2r_{i}\ge 2r_{i+2}ri​≥2ri+2​

根据带余除法的理论，有ri>ri+1r_{i}>r_{i+1}ri​>ri+1​。又因为ri=ri+1qi+1+ri+2r_{i}=r_{i+1}q_{i+1}+r_{i+2}ri​=ri+1​qi+1​+ri+2​，且qi+1≥1q_{i+1}\ge1qi+1​≥1，所以有

ri≥ri+2qi+1+ri+2≥2ri+2r_{i}\ge r_{i+2}q_{i+1}+r_{i+2}\ge2r_{i+2} ri​≥ri+2​qi+1​+ri+2​≥2ri+2​

因为

a=r0≥2r2r2≥2r4⋮rm−2≥2rma=r_{0}\ge2r_{2}\\ r_{2}\ge 2r_{4}\\ \vdots\\ r_{m-2}\ge 2r_{m} a=r0​≥2r2​r2​≥2r4​⋮rm−2​≥2rm​

并且迭代结束时rm+1=0r_{m+1}=0rm+1​=0，所以可以得出迭代次数为O(log⁡2a)O(\log_{2}a)O(log2​a)。同样可以得到O(log⁡2b)O(\log_{2}b)O(log2​b)。所以这里我们使用更为精确的界O(min{log⁡2a,log⁡2b})O(min\lbrace \log_{2}a,\log_{2}b\rbrace)O(min{log2​a,log2​b})。

由于每次迭代涉及两个整数的乘法，我们知道两个规模为nnn的整数相乘需要O(n2)O(n^{2})O(n2)次单位乘法，算上迭代次数，则Euclidean算法的单位乘法次数是O(n3)O(n^{3})O(n3)。这也是很多资料上给出的答案，但我们指出，这个上界可以进一步缩小至O(n2)O(n^{2})O(n2)。

证明：一方面，根据迭代方程，整个算法的单位乘法次数为∑i=1mlog⁡2qilog⁡2ri\sum\limits _{i=1}^{m}\log_{2}q_{i}\log_{2}r_{i}i=1∑m​log2​qi​log2​ri​

∑i=1mlog⁡2qilog⁡2ri≤log⁡2a×∑i=1mlog⁡2qi\sum_{i=1}^{m}\log_{2}q_{i}\log_{2}r_{i}\le \log_{2}a\times \sum_{i=1}^{m}\log_{2}q_{i} i=1∑m​log2​qi​log2​ri​≤log2​a×i=1∑m​log2​qi​

另一方面，根据迭代方程，有

a=r0>q1r1r1>q2r2⋮rm−1>qmrma=r_{0}>q_{1}r_{1}\\ r_{1}>q_{2}r_{2}\\ \vdots\\ r_{m-1}>q_{m}r_{m} a=r0​>q1​r1​r1​>q2​r2​⋮rm−1​>qm​rm​

左右分别相乘得到

a>∏i=1mqia>\prod\limits_{i=1}^{m}q_{i} a>i=1∏m​qi​

即

log⁡2a>log⁡2∏i=1mqi=∑i=1mlog⁡2qi\log_{2}a>\log_{2}\prod\limits_{i=1}^{m}q_{i}= \sum_{i=1}^{m}\log_{2}q_{i} log2​a>log2​i=1∏m​qi​=i=1∑m​log2​qi​

所以上界为

log⁡2a×∑i=1mlog⁡2qi<(log⁡2a)2\log_{2}a\times \sum_{i=1}^{m}\log_{2}q_{i}<(\log_{2}a)^{2} log2​a×i=1∑m​log2​qi​<(log2​a)2

令n=log⁡2an=\log_{2}an=log2​a，则算法的单位乘法次数为O(n2)O(n^{2})O(n2)。