c - GCD 函数的递归运行时间(欧几里德算法)

Question

我只能找到关于如何递归和迭代地实现 gcd 函数的帖子，但是我找不到这个。我确定它在 Stackoverflow 上，但是我找不到它，所以如果它是重复的帖子，我深表歉意。

我查看了维基百科( here )上的分析，无法理解它们的递归关系。

考虑以下在 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) + ???。现在分析递归调用，我不确定如何将 a (mod b) 解释为我的递归调用以正确说明我的递归关系。

Answer 1

在每个递归步骤中，gcd 会将其中一个参数(最多)减半。要看到这一点，请看以下两种情况:

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

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

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