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 时，它应该像这样运行: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 当 n 是奇数时？

我看了很多例子。 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)。