algorithm - Euclid 算法的时间复杂度

Question

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

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

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

score 83 · Accepted Answer

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

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

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

小A：2a <= b
小乙：2b <= a
小A：2a > b但是a < b
小B：2b > a但是b < a
平等的：a == b

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

Tiny A: b % (a % b) < aand 2a <= b, sob减少了至少一半, soa+b减少了至少25%
Tiny B: a % b < band 2b <= a, soa减少了至少一半, soa+b减少了至少25%
小A：b会变成b-a，小于，至少b/2减少。a+b25%
小B：a会变成a-b，小于，至少a/2减少。a+b25%
等于：a+b下降到0，显然a+b至少减少了25%。

因此，通过案例分析，每两步a+b至少减少25%. 在a+b强制低于1. S直到我们达到 0的总步数 ( ) 必须满足(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 倍的多对数因子。类似的东西 n^2 lg(n) 2^O(log* n)。可以通过使用二进制 gcd来避免多对数因子。

score 32 · Accepted Answer

分析算法的合适方法是确定其最坏情况。欧几里得 GCD 的最坏情况发生在涉及斐波那契对时。 void EGCD(fib[i], fib[i - 1]), 其中 i > 0。

例如，让我们选择被除数为 55，除数为 34 的情况（回想一下，我们仍在处理斐波那契数）。

在此处输入图像描述

您可能会注意到，此操作需要 8 次迭代（或递归调用）。

让我们尝试更大的斐波那契数，即 121393 和 75025。我们在这里也可以注意到它需要 24 次迭代（或递归调用）。

在此处输入图像描述

您还可以注意到，每次迭代都会产生一个斐波那契数。这就是为什么我们有这么多手术。我们确实不能仅使用斐波那契数来获得类似的结果。

因此，这次的时间复杂度将由小的 Oh（上限）表示。下限直观地是 Omega(1)：例如 500 除以 2 的情况。

让我们解决递归关系：

在此处输入图像描述

那么我们可以说欧几里得 GCD 最多可以进行 log(xy)操作。

score 19 · Accepted Answer

维基百科文章对此有很好的了解。

它甚至对值对有一个很好的复杂度图。

它不是O(a%b)。

众所周知（参见文章），它所采取的步骤永远不会超过较小数字中位数的五倍。所以最大步数随着位数的增加而增加(ln b)。每个步骤的成本也随着位数的增加而增加，因此复杂度受制于O(ln^2 b)其中 b 是较小的数字。这是一个上限，实际时间通常更少。

score 15 · Accepted Answer

见这里。

特别是这部分：

Lamé 表明，对于两个小于 n 的数，达到最大公约数所需的步数为

O(log min(a, b))一个好的上限也是如此。

score 9 · Accepted Answer

下面是对欧几里得算法运行时复杂度的直观理解。形式证明在各种文本中都有介绍，例如算法介绍和 TAOCP 第 2 卷。

首先考虑如果我们尝试对两个斐波那契数 F(k+1) 和 F(k) 取 gcd 会怎样。您可能很快就会观察到欧几里得算法迭代到 F(k) 和 F(k-1)。也就是说，每次迭代我们在斐波那契数列中向下移动一个数字。由于斐波那契数是 O(Phi ^ k)，其中 Phi 是黄金比例，我们可以看到 GCD 的运行时间是 O(log n)，其中 n=max(a, b) 并且 log 的基数是 Phi。接下来，我们可以通过观察斐波那契数始终产生对，其中余数在每次迭代中保持足够大并且永远不会变为零，直到您到达系列的开始，我们可以证明这将是最坏的情况。

我们可以使 O(log n) where n=max(a, b) 的界限更加紧密。假设 b >= a，所以我们可以在 O(log b) 处写入边界。首先，观察 GCD(ka, kb) = GCD(a, b)。由于 k 的最大值是 gcd(a,c)，我们可以在运行时将 b 替换为 b/gcd(a,b)，从而得到更严格的 O(log b/gcd(a,b)) 界限。

score 5 · Accepted Answer

以下是Mark Allen Weiss所著的Data Structures and Algorithm Analysis in C一书（第二版，2.4.4）中的分析：

Euclid 算法的工作原理是不断计算余数，直到达到 0。最后一个非零余数就是答案。

这是代码：

unsigned int Gcd(unsigned int M, unsigned int N)
{

    unsigned int Rem;
    while (N > 0) {
        Rem = M % N;
        M = N;
        N = Rem;
    }
    Return M;
}

这是我们将要使用的定理：

如果M > N，则M mod N < M/2。

证明：

有两种情况。如果 N <= M/2，则由于余数小于 N，因此该定理适用于这种情况。另一种情况是 N > M/2。但随后 N 进入 M 一次，余数 M - N < M/2，证明了定理。

所以，我们可以做出以下推论：

Variables    M      N      Rem

initial      M      N      M%N

1 iteration  N     M%N    N%(M%N)

2 iterations M%N  N%(M%N) (M%N)%(N%(M%N)) < (M%N)/2

所以，经过两次迭代，余数最多是其原始值的一半。这将表明迭代次数最多为2logN = O(logN).

请注意，算法计算 Gcd(M,N)，假设 M >= N。（如果 N > M，循环的第一次迭代交换它们。）

score 4 · Accepted Answer

欧几里得算法的最坏情况是每一步的余数都是最大的，即。斐波那契数列的两个连续项。

当 n 和 m 是 a 和 b 的位数时，假设 n >= m，算法使用 O(m) 除法。

请注意，复杂性总是根据输入的大小给出，在这种情况下是位数。

score 4 · Accepted Answer

当 n 和 m 都是连续的斐波那契数时，将出现最坏的情况。

gcd(Fn,Fn−1)=gcd(Fn−1,Fn−2)=⋯=gcd(F1,F0)=1，第n个斐波那契数是1.618^n，其中1.618是黄金比例。

因此，要找到 gcd(n,m)，递归调用的数量将是 Θ(logn)。

score 2 · Accepted Answer

Gabriel Lame 定理将步数限制为 log(1/sqrt(5)*(a+1/2))-2，其中 log 的底为 (1+sqrt(5))/2。这是算法的最坏情况，它发生在输入是连续的 Fibanocci 数时。

一个稍微宽松的界限是：log a，其中 log 的基数是 (sqrt(2)) 是 Koblitz 所暗示的。

出于加密目的，我们通常考虑算法的按位复杂度，考虑到位大小大约由 k=loga 给出。

下面详细分析欧几里得算法的位复杂度：

尽管在大多数参考文献中，欧几里德算法的按位复杂度由 O(loga)^3 给出，但存在一个更严格的界限，即 O(loga)^2。

考虑; r0=a, r1=b, r0=q1.r1+r2 。. . ,ri-1=qi.ri+ri+1, . . . ,rm-2=qm-1.rm-1+rm rm-1=qm.rm

观察到：a=r0>=b=r1>r2>r3...>rm-1>rm>0 ..........(1)

rm 是 a 和 b 的最大公约数。

通过 Koblitz 的书（A course in number Theory and Cryptography）中的一个声明可以证明：ri+1<(ri-1)/2 ....................( 2)

同样在 Koblitz 中，将 k 位正整数除以 l 位正整数（假设 k>=l）所需的位操作数为： (k-l+1).l ...... .............(3)

通过 (1) 和 (2) 划分的数量为 O(loga)，因此通过 (3) 的总复杂度为 O(loga)^3。

现在，通过 Koblitz 中的一句话，这可能会减少到 O(loga)^2。

考虑 ki=logri +1

通过 (1) 和 (2) 我们有： ki+1<=ki for i=0,1,...,m-2,m-1 和 ki+2<=(ki)-1 for i=0 ,1,...,m-2

并且由 (3) m divisons 的总成本为： SUM [(ki-1)-((ki)-1))]*ki for i=0,1,2,..,m

重新排列：SUM [(ki-1)-((ki)-1))]*ki<=4*k0^2

所以欧几里得算法的位复杂度是 O(loga)^2。

score 1 · Accepted Answer

然而，对于迭代算法，我们有：

int iterativeEGCD(long long n, long long m) {
    long long a;
    int numberOfIterations = 0;
    while ( n != 0 ) {
         a = m;
         m = n;
         n = a % n;
        numberOfIterations ++;
    }
    printf("\nIterative GCD iterated %d times.", numberOfIterations);
    return m;
}

对于斐波那契对，后者看起来iterativeEGCD()和在哪里没有区别，如下所示：iterativeEGCDForWorstCase()

int iterativeEGCDForWorstCase(long long n, long long m) {
    long long a;
    int numberOfIterations = 0;
    while ( n != 0 ) {
         a = m;
         m = n;
         n = a - n;
        numberOfIterations ++;
    }
    printf("\nIterative GCD iterated %d times.", numberOfIterations);
    return m;
}

是的，对于 Fibonacci Pairsn = a % n和n = a - n，它是完全一样的。

我们还知道，在对同一问题的较早答复中，存在一个普遍的递减因素：factor = m / (n % m)。

因此，为了以定义的形式塑造欧几里得 GCD 的迭代版本，我们可以将其描述为这样的“模拟器”：

void iterativeGCDSimulator(long long x, long long y) {
    long long i;
    double factor = x / (double)(x % y);
    int numberOfIterations = 0;
    for ( i = x * y ; i >= 1 ; i = i / factor) {
        numberOfIterations ++;
    }
    printf("\nIterative GCD Simulator iterated %d times.", numberOfIterations);
}

根据Jauhar Ali 博士的工作（最后一张幻灯片），上面的循环是对数的。

在此处输入图像描述

是的，小哦，因为模拟器最多告诉迭代次数。当在欧几里得 GCD 上进行探测时，非斐波那契对将需要比斐波那契更少的迭代次数。

score 1 · Accepted Answer

每一步都有两种情况

b >= a / 2，那么 a, b = b, a % b 将使 b 最多为之前值的一半

b < a / 2，那么 a, b = b, a % b 将使得 a 最多为之前值的一半，因为 b 小于 a / 2

所以在每一步，算法都会将至少一个数字减少到至少一半。

在最多O(log a)+O(log b)步骤中，这将简化为简单的情况。这产生了一个 O(log n) 算法，其中 n 是 a 和 b 的上限。

我在这里找到了

algorithm - Euclid 算法的时间复杂度

11 回答 11

Related

Reference