辗转相除法复杂度分析
斐波那契数列
文章图片
注：此时 
文章图片
文章图片
指数增长
F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）
欧几里得算法复杂度：
我们不妨设A>B>=1(若a
U0=a, U1=b, Uk=Uk-2 mod Uk-1 (k>=2)
若算法需要n次模运算, 则有
Un=gcd(a, b), Un+1=0
我们比较数列{Un}和菲波那契数列{Fn}
F0=0,F1=1<=Un ,F2=1<=Un-1
又因为由
Uk mod Uk+1=Uk+2
可得
Uk>=Uk+1+Uk+2(Uk=r·Uk+1+Uk+2,r>=1)
由数学归纳法得到 :
Uk>=Fn-k+1
于是得到:
A=U0>=Fn+1
B=U1>=Fn
也就是说如果欧几里得算法需要做n次模运算, 则B必定不小于Fn.
换句话说, 若 B
Fn>1.618n/√5
即
b>1.618n/√5
所以模运算的次数为 O( lg B ).
【辗转相除法复杂度分析】转载于:https://www.cnblogs.com/Bird-Xu/p/8180036.html
推荐阅读
- 陇上秋二|陇上秋二 罗敷媚
- 我执意要等，是因为我相信你一定会来
- 你不可不知的真相系列之科学
- 与狗狗的相处公式
- 滚这个字
- 我与阳光有氧的相遇（中下）
- 幸福的人都是相似的，所有幸福的女人，都做好了这2点
- 以太坊中的计量单位及相互转换
- 七绝·大相国寺怀古
- 问（现在多少家产相当于30年前的万元户（））