algorithm - 如何计算以下算法的时间复杂度

Question

如何计算以下算法的时间复杂度。我试过了，但我很困惑，因为递归调用。

power (real x, positive integer n)
//comment : This algorithm returns xn, taking x and n as input
{
    if n=1 then
    return x;
    y = power(x, |n/2|)
    if n id odd then
    return y*y*x //comment : returning the product of y2 and x
    else
    return y * y //comment : returning y2
}

有人可以用简单的步骤来解释。

Answer 1

要计算递归函数的时间复杂度，您需要根据某个输入变量计算将要进行的递归调用的次数N。

在这种情况下，每个调用最多进行一次递归调用。调用的数量大约为 O(log ₂ N)，因为每次调用都会减少N一半。

递归函数的其余部分是 O(1)，因为它不依赖于N. 因此，您的函数的时间复杂度为 O(log ₂ N)。

Answer 2

每个调用都被认为是一个常数时间的操作，它会递归多少次等于在n = 1之前你可以做多少次n/2，最多为log ₂ ( n) 次。因此，最坏情况下的运行时间是 O(log ₂n )。