你对递归算法的时间复杂度了解不够！

对于同一道题，使用同样的递归算法，有的同学写出O(n)的代码，有的同学写出O(logn)的代码代码。

这是为什么？

这就是你对递归的时间复杂度理解得不够透彻时会发生的事情！

接下来我会带大家做一道简单的面试题，模拟面试场景来逐步分析递归算法的时间复杂度，最终找到最优解。让我们看看如何将其写成 O(n 如果也是递归的) ) 代码。

面试题：求x的n次方

想一下这么简单的问题，代码应该怎么写。最直观的方式就是使用for循环来求结果。代码如下：

int function1(int x, int n) {
    int result = 1;  // 注意 任何数的0次方等于1
    for (int i = 0; i < n; i++) {
        result = result * x;
    }
    return result;
}

时间复杂度为O(n)。目前，面试官问道，是否有更高效的算法？

如果你现在不知道，不要说：我不知道怎么做，我不知道等等。 。

你可以和面试官讨论这个问题并问：“你能给我一些建议吗？”面试官问道：“考虑一下递归算法。”

然后你可以使用递归编写以下递归算法来解决这个问题。

int function2(int x, int n) {
    if (n == 0) {
        return 1; // return 1 同样是因为0次方是等于1的
    }
    return function2(x, n - 1) * x;
}

面试官问道：“那么这段代码的时间复杂度是多少？”。

有的同学看到递归可能会想到O(logn)。事实上，事实并非如此。递归算法的时间复杂度主要取决于： 递归次数 * 每个递归中执行的操作数。

我们再看一下代码。这在这里重复了多少次？

每次n-1，重复n次的时间复杂度为O(n)。每进行一次乘法运算，乘法运算的时间复杂度都是O(1)的常数项，因此这段代码的时间复杂度为n * 1 = O(n)。

这一次的复杂程度没有达到面试官的预期。于是我写了如下的递归算法代码：

int function3(int x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 1) {
        return function3(x, n / 2) * function3(x, n / 2)*x;
    }
    return function3(x, n / 2) * function3(x, n / 2);
}

面试官看到后微微一笑，问道：“这段代码的时间复杂度是多少？”说到这里，有的同学可能陷入了沉思。

我们来分析一下。首先，查看递归执行了多少次。我们得到了抽象递归的完整二叉树。刚刚同学写的算法可以用满二叉树来表示（为了表达方便，n选偶数16），如图：

当前二叉树必须找到x的第n次n 为 16。如果 n 为 16，需要进行多少次乘法运算？

这棵树中的每个节点都代表递归和乘法，因此递归的次数取决于树中节点的数量。

如果您熟悉二叉树，您应该知道如何查找满二叉树中的节点数。这棵满二叉树的节点数为 2^3 + 2^2 + 2^1 + 2^0 = 15。你会发现：这其实是一个等比数列加法公式。这个结论也经常出现在与二进制文件相关的面试问题中。

所以如果我们要求1之后的n次方，这个递归算法的时间复杂度仍然是O(n)。是的，你没有看错，仍然是 O(n) 时间复杂度！

面试官现在说“这个递归算法还是O(n)”，这显然没有达到面试官的预期。

那么如何写一个O(logn)的递归算法呢？

考虑刚刚给出的递归算法的代码。有什么多余的吗？事实上，计算是重复进行的。

所以我写了如下递归算法的代码：

int function4(int x, int n) {
    if (n == 0) {
        return 1;
    }
    int t = function4(x, n / 2);// 这里相对于function3，是把这个递归操作抽取出来
    if (n % 2 == 1) {
        return t * t * x;
    }
    return t * t;
}

现在我们来看看这段代码的时间复杂度？

还是看看这已经重复了多少次了。可以看到只有一次递归调用，而且每次都是n/2，所以这里我们调用了log base log总共2次n次。

每次递归都是一个乘法运算，这也是一个常量截止时间的运算，所以这个递归算法的时间复杂度确实是O(logn)。

当时大家终于写出了这样的代码，并且时间复杂度分析得很清楚。我相信面试官对此相当满意。

总结

关于递归的时间复杂度，初学者有时会一头雾水，解决过很多问题的老手仍然一头雾水。

在这篇文章中，我用一个非常简单的面试题：求x的n次方来一步步分析递归算法的时间复杂度。注意不要一看到递归就想到 O(logn)！

同样使用递归，有的同学可以写出O(logn)的代码，有的同学也可以写出O(n)的代码。

使用像function3这样的递归实现，很容易感觉它的时间复杂度是O(logn)，但它实际上是一个O(n)算法！

int function3(int x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 1) {
        return function3(x, n / 2) * function3(x, n / 2)*x;
    }
    return function3(x, n / 2) * function3(x, n / 2);
}

可见这道题很简单，但是也需要了解算法基础，尤其是递归。我采访别人的时候也用过这个问题，所以把整个场景写得那么真实。哈哈。

大公司面试时，最喜欢用简单的问题来测试候选人的算法能力。请注意，这里的“简单问题”可能并不容易！

如果你仔细阅读本文，相信你会对递归算法有一个新的认识。同样的问题也是递归，但是效率不一样！

来自程序员 Carl 编写的 Code Capriccio