我对欧几里德算法求最大公约数有疑问。
当p > q且q为n位整数时,求gcd(p,q)。
我正在尝试对该算法进行时间复杂度分析(输入如上所述为n位)。
gcd(p,q)
if (p == q)
return q
if (p < q)
gcd(q,p)
while (q != 0)
temp = p % q
p = q
q = temp
return p
我已经理解两个数字的和u+v
,其中u
和v
代表p
和q
的初始值,至少减少了1/2
的因素。
现在让m
成为此算法的迭代次数。
我们想找到最小的整数m
,使得(1/2)^m(u + v) <= 1
这是我的问题。
我知道每次迭代两个数字的总和上限为(1/2)^m(p + q)
。但我真的不明白为什么当这个数量<= 1
时,最大的m
被达到。
答案对于n位q
是O(n),但我卡在这里了。
请帮忙!!