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

Question

我无法确定Euclid最大公分母算法的时间复杂度.这个伪代码算法是:

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至少四分之一:

• 微小的一个: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.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可以避免多对数因子.

Answer 2

分析算法的合适方法是确定其最坏情况.Euclidean GCD的最坏情况发生在涉及Fibonacci Pairs时. void EGCD(fib[i], fib[i - 1]),其中i> 0.

例如,让我们选择股息为55,除数为34(回想我们仍在处理斐波那契数字)的情况.

您可能会注意到,此操作花费了8次迭代(或递归调用).

让我们尝试更大的Fibonacci数,即121393和75025.我们也可以注意到它需要24次迭代(或递归调用).

您还可以注意到每次迭代都会产生斐波纳契数.这就是我们有这么多业务的原因.我们不能仅用Fibonacci数得到类似的结果.

因此,时间复杂度将由小Oh(上限)表示,这次.下限是直观的Omega(1):例如500除以2的情况.

让我们解决递归关系:

我们可以说,然后欧几里德GCD可以使日志(XY)操作最多.

Answer 3

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

它甚至可以为价值对提供一个很好的复杂图.

事实并非如此O(a%b).

众所周知(见文章)它将永远不会采取比较小数字的数字的五倍更多的步骤.因此,最大步数随着数字的增加而增长(ln b).每个步骤的成本也随着数字的增加而增长,因此复杂性受O(ln^2 b)其中b是较小数字的约束.这是一个上限,实际时间通常较少.

Answer 4

看到这里.

特别是这部分:

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

所以O(log min(a, b))是一个很好的上限.

Answer 5

这是对Euclid算法的运行时复杂性的直观理解.正式证明包含在各种文本中,例如算法导论和TAOCP第2卷.

首先想想如果我们试图取两个Fibonacci数F(k + 1)和F(k)的gcd.你可能很快就会发现Euclid的算法迭代到F(k)和F(k-1).也就是说,每次迭代我们都会在Fibonacci系列中向下移动一个数字.由于Fibonacci数是O(Phi ^ k),其中Phi是黄金比率,我们可以看到GCD的运行时间是O(log n),其中n = max(a,b)并且log具有Phi的基数.接下来,我们可以通过观察Fibonacci数始终产生对,其中剩余部分在每次迭代中保持足够大并且在到达系列的开始之前永远不会变为零的情况下证明这将是最坏的情况.

我们可以使O(log n)n = max(a,b)更加紧密.假设b> = a,我们可以在O(log b)处写入绑定.首先,观察GCD(ka,kb)= GCD(a,b).由于k的最大值是gcd(a,c),我们可以在运行时用b/gcd(a,b)替换b,从而导致更严格的O界限(log b/gcd(a,b)).

Answer 6

以下是Mark Allen Weiss所著的《C 语言数据结构和算法分析》一书中的分析（第二版，2.4.4）：

欧几里得算法的工作原理是不断计算余数，直到达到 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，则循环的第一次迭代会交换它们。）

Answer 7

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

\n\n

gcd(Fn,Fn\xe2\x88\x921)=gcd(Fn\xe2\x88\x921,Fn\xe2\x88\x922)=\xe2\x8b\xaf=gcd(F1,F0)=1 和第 n 个斐波那契数字是 1.618^n，其中 1.618 是黄金比例。

\n\n

因此，要找到 gcd(n,m)，递归调用的次数将为 \xce\x98(logn)。

\n