algorithm - 欧几里得算法时间复杂度

Question

我有一个关于寻找最大公约数的欧几里德算法的问题。

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) .但我真的不明白为什么 max m当此数量为 <= 1 时达到.

n 位的答案是 O(n) q ，但这就是我遇到困难的地方。

请帮忙!!

Answer 1

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

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

2) q < p < 2*q:在这种情况下，模运算类似于从 p 中减去 q，因此总和最多为之前的 2/3。

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