递归运行GCD函数的时间(Euclid算法)

Question

我只能找到关于如何递归和迭代地实现gcd函数的帖子,但是我找不到这个.我确定它在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)解释为我的递归调用以正确陈述我的递归关系.

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.