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

Question

我很难确定欧几里德最大公分母算法的时间复杂度是多少。这个算法的伪代码是:

function gcd(a, b)
    while b ≠ 0
       t := b
       b := a mod b
       a := t
    return a

这似乎取决于a 和b。我的想法是时间复杂度是O(a % b)。那是对的吗？有更好的写法吗？

Answer 1

分析 Euclid 算法时间复杂度的一个技巧是跟踪两次迭代中发生的情况:

a', b' := a % b, b % (a % b)

现在 a 和 b 都会减少，而不是只有一个，这使得分析更容易。您可以将其分为以下情况:

• 小 A:2a <= b
• 小 B:2b <= a
• 小A:2a > b但是a < b
• 小B:2b > a但是b < a
• 等于:a == b

现在我们将证明每个案例都会减少总数 a+b至少四分之一:

• 小 A:b % (a % b) < a和 2a <= b , 所以 b至少减少了一半，所以a+b至少减少了 25%
• 小 B:a % b < b和 2b <= a , 所以 a至少减少了一半，所以a+b至少减少了 25%
• 小A:b将变为 b-a ，小于 b/2 ，递减 a+b至少 25% .
• 小B:a将变为 a-b ，小于 a/2 ，递减 a+b至少 25% .
• 等于:a+b下降到 0 , 明显减少 a+b至少 25% .

因此，通过案例分析，每双步递减a+b至少 25% .在 a+b 之前，这可能发生的次数最多被迫跌破1 .到达 0 之前的总步数 (S) 必须满足 (4/3)^S <= A+B .现在开始吧:

(4/3)^S <= A+B
S <= lg[4/3](A+B)
S is O(lg[4/3](A+B))
S is O(lg(A+B))
S is O(lg(A*B)) //because A*B asymptotically greater than A+B
S is O(lg(A)+lg(B))
//Input size N is lg(A) + lg(B)
S is O(N)

因此迭代次数与输入数字的数量成线性关系。对于适合 cpu 寄存器的数字，合理的做法是将迭代建模为采用常数时间并假装 gcd 的总运行时间是线性的。

当然，如果您要处理大整数，则必须考虑到每次迭代中的模数运算的成本不是恒定的。粗略地说，总的渐近运行时间将是多对数因子的 n^2 倍。 Something like n^2 lg(n) 2^O(log* n) .可以通过使用 binary gcd 来避免多对数因子。 .