algorithm - 计算递归算法的时间复杂度

Question

我正在尝试计算递归算法的时间复杂度，我想我已经差不多了。这是我一直在查看的伪代码:

long pow( long x, int n ) {
    if (n == 0)
        return 1;
    if (n == 1)
    return x;
    if(isEven(n))
        return pow(x, n / 2 ) * pow(x, n / 2);
    else
        return x * pow(x * x, n / 2);
} 

isEven 仅确定传递给它的整数是否为偶数，并且就本示例而言，在常数时间内运行。

因此，如果 n = 0 或 n = 1，则其操作具有恒定时间操作，如下所示: f(n) = C0。 然而，当 n > 1 时，它应该像这样运行: 当 n 为偶数时，f(n)= f(n-1) + f(n-1) + C1；当 n 为奇数时，f(n)= f(n-1) + 1，对吗？或者应该是:当 n 为偶数时，f(n)= f(n/2) + f(n/2) + C1；当 n 为奇数时，f(n)= f(n/2) + 1？

我看了很多例子。 Here我发现这非常有帮助。我的问题源于当 n 为偶数时有两次递归调用。我不完全确定在这里做什么。如果有人能指出我正确的方向，我将非常感激。

Answer 1

看看Master Theorem 。您可以将其视为“分而治之”算法。

最终结果是，通过两次递归调用，您最终会得到最坏情况的 O(n) 运行时间。例如。 pow(x, 4) 调用 pow(x, 2) 两次，pow(x, 1) 调用四次；一般来说，2 的幂将导致 n*2-1 次调用。

另请注意，只需调用 pow(x, n/2) 一次并对该分支中的结果求平方，算法就变为 O(log n)。