欧几里得的算法时间复杂度

Question

我对Euclid算法找到最大公约数有疑问.

gcd(p,q)其中p> q和q是n位整数.

我正在尝试对算法进行时间复杂度分析(输入是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).但我真的不明白为什么m达到这个数量的最大值<= 1.

对于n位q,答案是O(n),但这是我遇到的问题.

请帮忙!!

Answer 1

想象一下我们有 p 和 q，其中 p > q。现在，有两种情况：

1) p >= 2*q：在这种情况下，mod后p将减少到小于q，因此总和最多为之前的2/3。

2) q < p < 2*q：在这种情况下，mod 运算就像从 p 中减去 q，因此总和最多为之前的 2/3。

因此，在每一步中，该总和将是最后总和的 2/3。由于您的数字是 n 位，因此总和的大小为 2^{n+1}；因此，log 2^{n+1} (base 3/2) 步骤实际上是 O(n)，总和将为 0。