time-complexity - Euclid算法的时间复杂度减法

Question

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

    return a;
}

这个算法的时间复杂度是多少？有人可以提供详细的解释吗？

Answer 1

对于欧几里得减法算法，a和b是正整数。

最坏的情况是如果a = n和b = 1。然后，它将采取n - 1步骤计算GCD。因此，时间复杂度为 O(max(a,b)) 或 O(n)（如果它是根据迭代次数计算的）。

a顺便说一句，您还应该修复您的函数，以便它验证是否b真的是正整数。或者更好的是，您可以将您的返回和参数类型更改为unsigned long或unsigned int类似，并按照@templatetypedef 的建议，单独处理a = 0或b = 0单独处理案例。