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

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

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来避免多对数因子。 .