欧几里得算法时间复杂度

Question

我对欧几里德算法求最大公约数有疑问。

当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)，但我卡在这里了。

请帮忙！！

- namesake22

---

“p+q”在一步操作后被减半这种说法是不正确的。以“p=199”和“q=100”为例。 - Henry

我做了一些编辑。 - namesake22

它的时间复杂度为O（Log（min a，b）） - Alex Aparin

这可能会有所帮助 http://stackoverflow.com/a/18473133/2290983 - Amit Kumar

可能是欧几里得算法的时间复杂度的重复。 - maraca

@namesake22 我回答了你的问题吗？ - A. Mashreghi

Answer 1

假设我们有p和q，其中p>q。现在，有两种情况：

1）p>= 2*q：在这种情况下，在进行模运算后，p将被减少到小于q的某个值，因此总和最多只能是之前的2/3。

2）q<p<2*q：在这种情况下，模运算将像从p中减去q一样，因此总和仍然最多只能是之前的2/3。

因此，在每个步骤中，这个总和将是上一个总和的2/3。由于您的数字是n位，因此总和的大小为2^{n+1}；因此，使用log 2^{n+1}（基数为3/2）步骤，实际上是O（n），总和将为0。

- A. Mashreghi