我只能找到有关如何递归和迭代实现最大公约数函数的帖子,但我找不到这个。我确定它在Stackoverflow上,但是我找不到它,如果这是一个重复的帖子,我很抱歉。
我看了维基百科上(这里)的分析,但无法理解它们的递推关系。
考虑下面在C中递归实现的GCD函数实现。它有一个前提条件,即两个数字必须为正数,然而与运行时间无关。
我看了维基百科上(这里)的分析,但无法理解它们的递推关系。
考虑下面在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)以正确陈述我的递归关系。