GCD函数递归运行时间(欧几里德算法)
我只能找到关于如何递归地和迭代地实现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)解释为我的递归调用，以正确地声明我的递归关系。
回答 2
Stack Overflow用户
发布于 2013-08-08 22:28:34
在每个递归步骤中，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的最大值。
Stack Overflow用户
发布于 2014-03-12 01:17:13
要分析欧几里德GCD，您应该使用Fibonacci对: gcd( Fibn，Fibn- 1) --最坏的情况。
如果您测试上面的欧几里德GCD，您将得到24个递归调用。
如果您习惯于解决重复关系，那么您可能感兴趣的有以下几点：
通过这项研究，我们无法推导出任何除数/除数对的确切迭代次数(因此是小的Oh表示法)，但是它保证了这个上界是有效的。通常，下界是Omega(1) (例如，当除数为1时)。
https://stackoverflow.com/questions/18137019
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号