- gcd(a, b) = gcd(b, r) r=a%b
每调用一次gcd，需要计算一次a%b，所以gcd的时间复杂度可用a%b的执行次数衡量。 - Finonacci序列 1, 2, 3, 5, 8, 13, ...f1 =1, f2=2, ...fk=fk-1+fk-2
a
|
b
|
求余运算次数
|
1
|
0
|
0
|
2
|
1
|
1
|
3
|
2
|
2
|
5
|
3
|
3
|
8
|
5
|
4
|
13
|
8
|
5
|
21
|
13
|
6
|
从上图出发，可以假设若欧几里德算法执行n次时，a>=fn+1, b>=fn
证明：
当n=1时假设成立，假设在n时成立，只需证当n+1时成立即可
假设 gcd(a, b)需要执行n+1次，r=a%b, 则 gcd(b, r)需要执行n次
所以有 b>=fn+1，r>=fn，a = bq + r >= b + r >=fn+1 + fn = fn+2
从而有a>=fn+2， b>=fn+1 所以假设在n+1时也成立
No comments:
Post a Comment