皮皮哥让你彻底搞懂递归时间复杂度

recursive-soup

皮皮哥编码10载,看过很多程序员简历上写着熟悉数据结构和算法,但是对于时间复杂度稍微深入点的问题,都回答的不怎么样,其实还是没懂

算法分顺序和递归,顺序的算法时间复杂度我就不多讲,一般的懂大O计数法的都明白,本次着重讲讲递归

搞懂算法时间复杂度是一个普通程序员和优秀程序员的分水岭,毕竟写出O(lgn)和O(n!)的时间复杂度的区别特别大

先来看letcode一道题,

泰波那契序列 Tn 定义如下:

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n,请返回第 n 个泰波那契数 Tn 的值。

示例 1:

输入:n = 4
输出:4
解释:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
示例 2:

输入:n = 25
输出:1389537

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/n-th-tribonacci-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

这是一道经典面试题,属于斐波那契数的升级版,很多人很快的写出算法

/**
 * @param {number} n
 * @return {number}
 */
const tribonacci = (n) => {
  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  } else if (n === 2) {
    return 1;
  }
  return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
};

当然这道试题这样写会超时,原因就不细说了,这个时候面试官会问你这么写的算法时间复杂度是多少
有的同学可能一看到递归就想到了logn,其实并不是这样,问他是怎么算的,他好像并不知道

递归树求解

来看一下这道面试题:求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;
}

面试官问:那么这份代码的时间复杂度是多少?

有的同学可能一看到递归就想到了logn,其实并不是这样

递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数

那我们再来看代码,我们递归了几次呢。

每次n-1,递归了n次 时间复杂度是O(n),每次进行了一个乘法操作,乘法操作的时间复杂度一个常数项O(1)

所以这份代码的时间复杂度是 n * 1 = O(n)

这个时间复杂度可能就没有达到面试官的预期。

于是同学又写出了这样的一个递归的算法的代码如下 ,来求 x的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为偶数),如图:

当前这颗二叉树就是求x的n次方,n为16的情况

n为16的时候 我们进行了多少次乘法运算呢

这棵树上每一个节点就代表着一次递归并进行了一次相乘操作

所以 进行了多少次递归的话,就是看这棵树上有多少个节点。

熟悉二叉树的同学应该知道如何求满二叉树节点数量

这颗满二叉树的节点数量就是2^3 + 2^2 + 2^1 + 2^0 = 15

有同学就会发现 这其实是等比数列的求和公式, 如果不理解的同学可以直接记下来这个结论。

这个结论在二叉树相关的面试题里也经常出现。

这么如果是求x的n次方,这个递归树有多少个节点呢,如下图所示

831631635715_.pic

时间复杂度忽略掉常数项-1之后,我们发现这个递归算法的时间复杂度依然是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以2为底n的对数次

每次递归了做都是一次乘法操作,这也是一个常数项的操作,

所以说这个递归算法的时间复杂度才是真正的O(logn)。

如果同学们最后写出了这样的代码并且时间复杂度分析的非常清晰,相信面试官是比较满意的。

最后希望通过这么一个简单的面试题,让大家真正了解了递归算法的时间复杂度该如何分析。

主定理

介绍一个叫主定理的东西,这个定理为什么重要,就是因为这个主定理的话,其实它是用来解决所有递归的函数,怎么来计算它的时间复杂度。主定理本身的话,数学上来证明相对比较复杂(关于主定理可以参考维基百科:https://zh.wikipedia.org/wiki…)

也就是说,任何一个分治或者递归的函数,都可以算出它的时间复杂度,怎么算就是通过这个主定理。本身比较复杂的话,那怎样化简为实际可用的办法,其实关键就是这四种,一般记住就可以了

一般在各种递归的情形的话,有上边这四种情形,是在面试和平时工作中会用上

二分查找(Binary search):一般发生在一个数列本身有序的时候,要在有序的数列中找到目标数,所以它每次都一分为二,只查一边,这样的话,最后它的时间复杂度是O(logn)

二叉树遍历(Binary tree traversal):如果是二叉树遍历的话,它的时间复杂度为O(n)。因为通过主定理可以知道,它每次要一分为二,但是每次一分为二之后,每一边它是相同的时间复杂度。最后它的递推公式就变成了图中T(n)=2T(n/2)+O(1)这样。最后根据这个主定理就可以推出它的运行时间为O(n)。当然这里也有一个简化的思考方式,就是二叉树的遍历的话,会每一个节点都访问一次,且仅访问一次,所以它的时间复杂度就是O(n)

二维矩阵(Optimal sorted matrix search):在一个排好序的二维矩阵中进行二分查找,这个时候也是通过主定理可以得出时间复杂度是O(n),记住就可以了

归并排序(merge sort):所有排序最优的办法就是nlogn,归并排序的时间复杂度就是O(nlogn)

再附一张主定理的计算方法,目前只找到的比较好的资料

总结

递归可以使用递归树或者主定理去求解,需要多做题去掌握,下次千万不要碰到递归说是O(logn)了,如果有问题欢迎指正

再分享一个学习算法和数据结构的秘籍,请大力点击,多看看,这个作者把算法总结成成了套路
https://labuladong.gitee.io/algo/1/2/

9赞

课后作业

求整数n (n>=0)阶乘的算法如下,其时间复杂度是( )

int fact(int n){
    if (n<=l) return 1;
    return n*fact(n-1);
}

题2写一道算法题

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制:

0 <= 数组长度 <= 50000

/**

* @param {number[]} nums

* @return {number}

*/

var reversePairs = function(nums) {

};
1赞

好硬的知识啊 :innocent:

这个名词,我记得上次看到还是在大学~

其实这个知识点非常重要啊,不懂的话写出的代码效率会很一般

mark~~

如果当年好好学算法和数据结构 :rofl:。。。

回头看这句话,其实很多东西我当年其实还是不能理解,主要还是自己当时能力有限,工作几年以后,慢慢再去品这些计算机经典教材,受益匪浅

你这个剩饭残羹的配图真是恶心心呀

当年毕业前好好找个女朋友

多多补充几个算法就好了

:innocent:这个是一个很形象得表现出递归得图,参考的一篇国外论文

这个 l 是哪来的呢,是 1 吗

是1,抱歉打字笔误了

那第一题我会,在原文里我就找到答案了