4

我只能找到关于如何递归和迭代地实现 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) + ???。现在要分析递归调用，我不确定如何将 a (mod b) 解释为我的递归调用以正确说明我的递归关系。

4

3 回答 3

10

在每个递归步骤中，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。

于 2013-08-08T22:28:34.133 回答
1

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

如果你在上面测试你的欧几里得 GCD，你最终会得到 24 个递归调用。

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

在此处输入图像描述

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

于 2014-03-12T01:17:13.200 回答
0

一个简单的分析和证明是这样的：

  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)数量与 in 相同EUCLID(a,b)，其中k是某个整数。

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

于 2015-05-01T17:53:53.343 回答