Euclidalgorithm的时间复杂度

我很难判断Euclid的最大公分母algorithm的时间复杂度是多less。 这个伪码的algorithm是：

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

这似乎取决于a和b 。 我的想法是时间复杂度是O（a％b）。 那是对的吗？ 有没有更好的方式来写这个？

Answer 1

分析Euclidalgorithm的时间复杂度的一个技巧是遵循两次迭代的结果：

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

现在a和b都会减less，而不是只有一个，这使得分析更容易。 你可以把它分成几个例子：

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

现在我们将显示每一个情况都会使a+b总数减less至less四分之一：

• 小A： b % (a % b) < a和2a <= b ，所以b至less减半，所以a+b至less减less25%
• 微小的B： a % b < b和2b <= a ，所以a减less至less一半，所以a+b减less至less25%
• 小A： b将变成小于b/2 ba ，将a+b减less至less25% 。
• 小B： a将变成ab ，小于a/2 ， a+b至less减less25% 。
• 等于： a+b下降到0 ，这显然会使a+b下降至less25% 。

因此，通过案例分析，每一步都会使a+b降低至less25% 。 在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) 

所以迭代次数在input数字的数量上是线性的。 对于符合CPU寄存器的数字，将迭代build模为恒定时间并假设gcd的总运行时间是线性是合理的。

当然，如果你要处理大整数，你必须考虑到每次迭代中的模数运算没有固定成本的事实。 粗略地说，总的渐近运行时间将是多对数因子的n ^ 2倍。 像 n^2 lg(n) 2^O(log* n) 。 多聚对数因子可以通过代替使用二进制gcd来避免。

Answer 2

分析algorithm的合适方法是确定其最差情况。 欧几里德GCD最糟糕的情况发生在斐波那契对。 void EGCD(fib[i], fib[i - 1]) ，其中i> 0。

例如，我们select红利为55，除数为34的情况（记得我们仍在处理斐波纳契数字）。

你可能会注意到，这个操作花费了8次迭代（或recursion调用）。

让我们试试更大的斐波纳契数字，即121393和75025.我们也可以注意到，它花了24迭代（或recursion调用）。

你也可以注意到每次迭代产生一个斐波那契数。 这就是为什么我们有这么多的操作。 我们不能只用斐波纳契数字得到类似的结果。

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

我们来解决这个复发关系：

我们可以这么说，欧几里得GCD最多可以做log（xy）操作。

Answer 3

维基百科的文章中有很好的一面 。

它甚至具有价值对的复杂情节。

这不是O（a％b）。

据了解（见文章），它将永远不会超过小数字位数的五倍。 所以最大的步数随着数字的位数（ln b）而增长。 每个步骤的成本也随着数字的数量而增长，所以复杂度受O（ln ^ 2 b）的约束，其中b是较小的nubmer。 这是一个上限，实际时间通常较less。

Answer 4

看到这里 。

特别是这个部分：

拉米表明，需要达到两个数字小于n的最大公约数的步骤是

所以O(log min(a, b))是一个好的上界。

Answer 5

这里直观的了解了Euclidalgorithm的运行时复杂性。 正式的certificate包括在algorithm介绍和TAOCP第2卷等各种文本中。

首先想想如果我们试图采用两个斐波纳契数字F（K + 1）和F（K）的gcd是什么。 你可能会很快观察到Euclidalgorithm迭代到F（k）和F（k-1）。 也就是说，在每次迭代中，我们将向下移动斐波那契数列中的一个数字。 由于斐波纳契数是O（Phi ^ k），其中Phi是黄金比例，所以我们可以看到GCD的运行时间是O（log n），其中n = max（a，b）并且log具有Phi的基数。 接下来，我们可以certificate这是最糟糕的情况，通过观察斐波那契数字在每次迭代中始终保持足够大并且在到达序列开始之前永远不会变为零。

我们可以使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

欧几里德algorithm最糟糕的情况是当剩下的每一步都是最大的时候， 连续两个斐波那契数列。

当n和m是a和b的位数时，假设n> = m，algorithm使用O（m）个划分。

请注意，总是以input的大小来表示复杂度，在这种情况下是数字的数量。

Answer 7

然而，对于迭代algorithm，我们有：

 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; } 

对于Fibonacci对， 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; } 

是的，对于斐波那契对， n = a % n和n = a - n ，这完全一样。

我们也知道，在同一个问题的早期回答中，有一个普遍的下降因素： factor = m / (n % m) 。

因此，为了定义forms的欧几里德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上进行探测时，非Fibonacci对比Fibonacci的迭代次数要less。

Answer 8

加布里埃尔·拉梅定理通过log（1 / sqrt（5）*（a + 1/2）） – 2来限定步长数，其中log的基数是（1 + sqrt（5））/ 2。 这是针对该algorithm的最糟糕情况，并且当input是连续的Fibanocci数字时发生。

稍微更自由的界限是：log a，其中日志的基础是（sqrt（2））是由Koblitz暗示的。

为了encryption的目的，我们通常考虑algorithm的逐位复杂性，考虑到位大小大约由k = loga给出。

下面是Euclidalgorithm按位复杂度的详细分析：

虽然在大多数参考文献中，欧几里德algorithm的按位复杂度由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的书中（一个数论和密码学的课程）可以certificate：ri + 1 <（ri-1）/ 2 ……………..（ 2）

再次在Koblitz中，将k位正整数除以1位正整数（假设k> = 1）所需的位操作数目为：（k-1 + 1）.1 …… ………….（3）

由（1）和（2）的分配数是O（loga），所以（3）总的复杂度是O（loga）^ 3。

现在这可以通过在Koblitz的一个评论减less到O（loga）^ 2。

考虑ki = logri + 1

对于i = 0,1，…，m-2，m-1和ki + 2 <=（ki）-1，我们有：ki + 1 <= ki ，1，…，M-2

（3）m个分割的总成本由下式限定：SUM（（ki-1） – （（ki）-1））] ki对于i = 0,1,2，…，m

重新排列：SUM [（ki-1） – （（ki）-1））] * ki <= 4 * k0 ^ 2

所以欧几里得algorithm的按位复杂度是O（loga）^ 2。