GCD函数递归运行时间（欧几里得算法）

Question

我只能找到有关如何递归和迭代实现最大公约数函数的帖子，但我找不到这个。我确定它在Stackoverflow上，但是我找不到它，如果这是一个重复的帖子，我很抱歉。

---

我看了维基百科上（这里）的分析，但无法理解它们的递推关系。

考虑下面在C中递归实现的GCD函数实现。它有一个前提条件，即两个数字必须为正数，然而与运行时间无关。

int gcd( int const a, int const b ) {
  // Checks pre conditions.
  assert( a >= 0 );
  assert( b >= 0 );

  if ( a < b ) return gcd( b, a );

  if ( b == 0 ) return a;

  return gcd( b, a % b );
}

在运行时间上进行分析，我发现每个操作都是O（1），因此我们知道到目前为止的递归关系是：T（n）= O（1）+???。现在要分析递归调用，我不确定如何解释（mod b）以正确陈述我的递归关系。

在运行时间上进行分析，我发现每个操作都是O（1），因此我们知道到目前为止的递归关系是：T（n）= O（1）+ ???. 现在要分析递归调用，我不确定如何解释（mod b）以正确陈述我的递归关系。

- Jacob Pollack

---

https://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency - Shwetabh Shekhar

Answer 1

在每个递归步骤中，gcd会将其中一个参数减半（最多）。为了理解这一点，请看这两种情况：

如果 b >= a/2，那么下一步你将得到 a' = b 和 b' < a/2，因为 % 操作将从 a 中移除 b 或更多。

如果 b < a/2，那么下一步你将得到 a' = b 和 b' < a/2，因为 % 操作最多可以返回 b - 1。

因此，在每个递归步骤中，gcd会将其中一个参数减半（最多），这需要 O(log(N)) 步，其中 N 是初始 a 和 b 的最大值。

- Doug Currie

Answer 2

要分析欧几里得算法的最坏情况下，应该使用斐波那契数对：gcd(Fib[n], Fib[n - 1])。

如果您测试上述欧几里得算法，则将得到24个递归调用。

如果您习惯于解决递归关系，则可能会对以下内容感兴趣：

通过这项研究，无法推断任何被除数/除数对的确切迭代次数（因此使用小Oh符号），但它保证了这个上限是有效的。通常，下限为Omega(1)（例如，当除数为1时）。

- Mohamed Ennahdi El Idrissi

Answer 3

一个简单的分析和证明如下：

1. 证明如果 Euclid(a,b) 执行超过 N 步骤，则有 a>=F(n+1) 和 b>=F(n)，其中 F(i) 是第 i 个斐波那契数。
   这可以通过归纳法轻松完成。

2. 证明 F(n) ≥ φ^n-1，同样是通过归纳法。

3. 利用步骤1和2的结果，我们有 b ≥ F(n) ≥ φ^n-1
   双方取对数， log_φb ≥ n-1.
   
   因此证明了，n ≤ 1 + log_φb

这个界限可以被改进。
在EUCLID(ka,kb)中的递归调用次数与EUCLID(a,b)中的相同，其中k是某个整数。

因此，该界限被改进为1 + log_φ( b / gcd(a,b) )。

- anaik