gcd算法的时间复杂度

Question

int gcd(int a, int b){
if (a==b) return (a);
else
{
if (a > b) return (gcd(b, a-b));
else return (gcd(a, b-a));
}
}

我发现这个算法的复杂度是T(n(=2T(n-1(+5，对吗？如果是，我如何应用Master定理来找到时间复杂度类？

Answer 1

您没有定义n，算法的时间复杂性不取决于单个参数。

例如，假设n = max(a, b)，我们有

T(a, a) = O(1)
T(a, 1) = O(n).

Answer 2

这个算法的复杂度是T(n(=2T(n-1(+5，对吗？

不，不是。您只有一个递归调用，并且没有将问题拆分为两个较小的问题，正如您的公式所暗示的那样。

你不能使用主定理，当你有类似T(n)=aT(n-1)+f(n)的东西时，你需要T(n)=aT(n/b)+f(n)。因此，每次递归调用都必须将问题大小除以相同的值。

对于该版本，时间复杂度为O(n)，其中n = max(a,b)或n=a+b。最坏的情况是，当您输入gcd(n,n+1)或gcd(1,n)时，您只需减去1n-1次。

在最好的情况下(输入不相同(，输入两个连续的斐波那契数，然后得到对数复杂度。减法版本的最佳情况与欧几里德算法的模版本的最坏情况相同。事实上，在这种情况下，它们之间没有区别。

取模欧几里得算法的时间复杂度为O(log(n))，其中n = max(a,b)或n=a+b。当你看斐波那契数时，你可以得到这种复杂性。它们是该算法的最坏情况，并且呈指数级增长。欧几里得算法对这些数字进行(向后，方向无关紧要(，因此复杂性是指数函数的倒数，因此log(n((基数无关紧要(