刷题指南-1

博士读了一年，开始捡起来代码算法功底。今天主要任务是熟悉ACM模式的IO，并为后面刷题做准备。
其次是学习了递归算法的时间复杂度。

主要的练习题目有俩个：A+B-1 及 A+B-2

https://kamacoder.com/

  while True:
    try:
        num=input()
        if None:
            break
        for i in range(int(num)) :
            num_list=input().split(" ")
            print(int(num_list[0])+int(num_list[1]))
    except :
        break

while True:
    try:
        input_list = input().split(' ')
        if len(input_list) == 0:
            break
        if len(input_list) == 2:
            print(int(input_list[0])+int(input_list[1]))
    except:
        break

本篇通过一道面试题，一个面试场景，来好好分析一下如何求递归算法的时间复杂度。

相信很多同学对递归算法的时间复杂度都很模糊，那么这篇来给大家通透的讲一讲。

同一道题目，同样使用递归算法，有的同学会写出了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(log n)，其实并不是这样，递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数。

那再来看代码，这里递归了几次呢？

每次n-1，递归了n次时间复杂度是O(n)，每次进行了一个乘法操作，乘法操作的时间复杂度一个常数项O(1)，所以这份代码的时间复杂度是 n × 1 = O(n)。

这个时间复杂度就没有达到面试官的预期。于是又写出了如下的递归算法的代码：

int function3(int x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;

    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），如图：

image.png

当前这棵二叉树就是求x的n次方，n为16的情况，n为16的时候，进行了多少次乘法运算呢？

这棵树上每一个节点就代表着一次递归并进行了一次相乘操作，所以进行了多少次递归的话，就是看这棵树上有多少个节点。

熟悉二叉树话应该知道如何求满二叉树节点数量，这棵满二叉树的节点数量就是2^3 + 2^2 + 2^1 + 2^0 = 15，可以发现：这其实是等比数列的求和公式，这个结论在二叉树相关的面试题里也经常出现。

这么如果是求x的n次方，这个递归树有多少个节点呢，如下图所示：(m为深度，从0开始)

image.png

时间复杂度忽略掉常数项-1之后，这个递归算法的时间复杂度依然是O(n)。对，你没看错，依然是O(n)的时间复杂度！