欧几里得算法
function Euclid(a;
b)
1: if b = 0 then
2: return a;
3: end if
4: return Euclid(b;
a mod b);
复杂度分析:
设 a>=ba >= b ,则有 amodb
假设a=bq+ra = b q + r ,其中q>=1q >= 1 ,且 0<=r
r=a?bq
因此:
aa 于是:
11+q×a
==> aq1+q?bq<0a q 1 + q ? b q < 0
==> aq1+q+a1+q?bq
所以有: a?bq
于是复杂度为: min(O(loga),O(logb))m i n ( O ( l o g a ) , O ( l o g b ) )即O(logn)