ユークリッドアルゴリズムの実現、正確性証明及び時間複雑度分析

最大公約数を求める最も一般的なアルゴリズムはユークリッドアルゴリズムであり,転がり相除法とも呼ばれる.問題はiとjの最大公約数gcd(i,j)を求めると定義され、iとjは整数であり、i>jを設定してもよい.アルゴリズムは再帰的に表すことができる:

1.  j   i,  gcd(i,j)=j;
2.j    i, r=i%j,  gcd(i,j)=gcd(j,r).

上のアルゴリズムはiに対して
 
C言語で実現:

int gcd(int i, int j)
{
    int r = i % j;
    return r == 0 ? j : gcd(j, r);
} 

　　
アルゴリズムの正確性分析
次の一歩一歩の切り込み
証明する前に一つの説明を見る:二つの数i=mdに対して、j=nd.i,jの最大公約数はdの要件としてmとnの相互質である.
もう1つの説明を参照すると、mとnが互いに結合する場合、(m−kn)とnも互いに結合する.これは逆法を用いることができる:(m−kn)とnが互いに質を持たないと仮定すると、(m−kn)=enとなる因子eが存在する.ではm=(k+e)nは,m,nの相互質の問題条件に反するため仮定は成り立たない.(m−kn)とnも互質である.
アルゴリズムのステップ1は、これが最大公約数の定義であるため、明らかに成立している.アルゴリズムのステップ2:実はアルゴリズムが証明する目標はr=i%j!=0の場合、gcd(i,j)=gcd(j,r)となる.既知の条件によれば、dがi,jの最大公約数であるとすると、i=md,j=ndとなり、ここでm,nは相互質である.(m,nが互いに質を持たない場合、dは最大公約数ではない)(現在探しているのはgcd(j,r)の最大公約もdである場合、rをdで表し、この式の係数とnが質を持つことを証明すると、dはrとjの最大公約数である)次に、r=i%jのため、i=kj+rのうちk>=1,k=[m/n]は、上記の式に持ち込まれる:md=kndrであるため、r=(m-kn)dは、またj=nd,nと(m−kn)は互いに質的であるため,dはj,rの最大公約数である.
 

     1,    (       ).        2.
 d i j      ,
  i=md,j=nd,m n  (  d       ).
 r=i%j    i=kj+r,k=⌊m/n⌋,k≥1(       i>j).
 i=md,j=nd    
md=knd+r
  
r=(m-kn)d
m-kn m     .
    d j r      .

　
じかんふくごうどぶんせき
このアルゴリズムを逆に見ると、最後の余数は0で、最後の2回目の余数はdで、最後の3回目はkdで、k>1...1つの数列を構成するため、{0,d,kd,nkd+d,...}数列のn項にn+1項を加え、n+2項より小さいため、フィボナッチ数列よりも成長が速い.フィボナッチ数列の成長速度は指数であることが知られており、分析される数列も指数成長である.ユークリッドアルゴリズムをk回必要とすると、j=O(2^k)、k=O(lg j)となる.だからユークリッドアルゴリズムは最大公約数を求める時間の複雑度は対数級で、速度は非常に速い.
 
転載先:https://www.cnblogs.com/stemon/p/4720013.html