欧几里得算法的一些秘密
1、欧几里得算法的最坏运行时间——斐波那契数列
欧几里得算法的一般运行次数是取决于 a , b a,b a,b的位数。
欧几里得算法: g c d ( a , b ) = g c d ( b , a m o d b ) gcd(a,b)=gcd(b,a\:mod\:b) gcd(a,b)=gcd(b,amodb)
显然,最终答案是 g c d ( r , 0 ) gcd(r,0) gcd(r,0) ,此时递归返回 g d c = r gdc = r gdc=r
欧几里得算法的运行时间,就取决与递归的次数 k k k。
递归过程:
g c d ( a , b ) → g c d ( b , a m o d b ) → . . . → g c d ( r , 0 ) gcd(a,b)\rightarrow gcd(b,a\:mod\:b)\rightarrow ...\rightarrow gcd(r,0) gcd(a,b)→gcd(b,amodb)→...→gcd(r,0)
逆过来:
g c d ( r , 0 ) → g c d ( k 1 ( r ) , r ) → g c d ( k 2 ( k 1 r ) + r , k 1 r ) → g c d ( k 3 ( k 2 k 1 r + r ) + k 1 r , k 2 k 1 r + r ) → . . . → g c d ( a , b ) gcd(r,0)\rightarrow gcd(k_1(r),r)\rightarrow gcd(k_2(k_1r)+r,k_1r)\rightarrow gcd(k_3(k_2k_1r+r)+k_1r\:,\:k_2k_1r+r)\rightarrow ...\rightarrow gcd(a,b) gcd(r,0)→gcd(k1(r),r)→gcd(k2(k1r)+r,k1r)→gcd(k3(k2k1r+r)+k1r,k2k1r+r)→...→gcd(a,b)
g c d ( k 4 ( k 3 k 2 k 1 r + ( k 1 + k 3 ) r ) + ( k 2 k 1 r + r ) , k 3 k 2 k 1 r + ( k 1 + k 3 ) r ) gcd(k4(k_3k_2k_1r+(k_1+k_3)r)+(k_2k_1r+r),k_3k_2k_1r+(k_1+k_3)r) gcd(k4(k3k2k1r+(k1+k3)r)+(k2k1r+r),k3k2k1r+(k1+k3)r)
我们可以观察,每个 g c d ( a , b ) gcd(a,b) gcd(a,b)中 a a a的变化:
r → k 1 r → k 2 k 1 r + r → k 3 ( k 2 k 1 r + r ) + k 1 r → k 4 ( k 3 ( k 2 k 1 r + r ) + k 1 r ) + ( k 2 k 1 r + r ) → . . . r\rightarrow k_1r\rightarrow k_2k_1r+r\rightarrow k_3(k_2k_1r+r)+k_1r\rightarrow k4(k_3(k_2k_1r+r)+k_1r)+(k_2k_1r+r) \rightarrow... r→k1r→k2k1r+r→k3(k2k1r+r)+k1r→k4(k3(k2k1r+r)+k1r)+(k2k1r+r)→...
f ( 0 ) → f ( 1 ) → f ( 2 ) → . . . → f ( n ) f(0)\rightarrow f(1)\rightarrow f(2)\rightarrow ...\rightarrow f(n) f(0)→f(1)→f(2)→...→f(n)
可以发现满足一个这样的性质:
f ( i ) m o d f ( i − 1 ) = f ( i − 2 ) f(i)\:mod\:f(i-1)=f(i-2) f(i)modf(i−1)=f(i−2)
所以, a a a的变化可以写成: f ( i ) = k f ( i − 1 ) + f ( i − 2 ) ≥ f ( i − 1 ) + f ( i − 2 ) = F i b o n a c c i ( i ) = F ( i ) f(i) = kf(i-1)+f(i-2) \geq f(i-1)+f(i-2) = Fibonacci(i)=F(i) f(i)=kf(i−1)+f(i−2)≥f(i−1)+f(i−2)=Fibonacci(i)=F(i)
所以简化递归过程:
f a ( 0 ) = r → f a ( 1 ) = k 1 f a ( 0 ) → f a ( 2 ) = k 2 f a ( 1 ) + f a ( 0 ) → . . . f_a(0)=r \rightarrow f_a(1)=k_1f_a(0) \rightarrow f_a(2)=k_2f_a(1)+f_a(0) \rightarrow... fa(0)=r→fa(1)=k1fa(0)→fa(2)=k2fa(1)+fa(0)→...
f b ( 0 ) = 0 → f b ( 1 ) = f a ( 0 ) → f b ( 2 ) = f a ( 1 ) → . . . f_b(0)=0\rightarrow f_b(1)=f_a(0)\quad\rightarrow f_b(2)=f_a(1)\rightarrow... fb(0)=0→fb(1)=fa(0)→fb(2)=fa(1)→...
所以,我们令 k , r = 1 k,r=1 k,r=1
可以得到一个数组 F a : 1 , 1 , 2 , 3 , . . . , F_a:1,1,2,3,..., Fa:1,1,2,3,...,( a a a的变化过程)
就可以得到 a , b a,b a,b递归 k k k次的最小取值: a = F a ( k + 2 ) , b = F a ( k + 1 ) a = F_a(k+2),b=F_a(k+1) a=Fa(k+2),b=Fa(k+1)。
g c d ( F ( k + 2 ) , F ( k + 1 ) ) = g c d ( F ( k + 1 ) , F ( k + 2 ) m o d F ( k + 1 ) ) = g c d ( F ( k + 1 ) , F ( k ) ) gcd(F(k+2),F(k+1)) = gcd(F(k+1),F(k+2)\:mod\:F(k+1))= gcd(F(k+1),F(k)) gcd(F(k+2),F(k+1))=gcd(F(k+1),F(k+2)modF(k+1))=gcd(F(k+1),F(k))
注意:上述的递归 k k k次的最小取值,仅在 a > b ≥ 0 a>b\geq0 a>b≥0 的情况下。
所以,我们就可以通过, a , b a,b a,b的取值,大概判断,调用的次数。