网易考拉的网站建设,建网方案策划书,北京网站设计方案,深圳 网站托管这是磊哥的第 189 期分享作者 | 田小齐来源 | 码农田小齐#xff08;ID#xff1a;NYCSDE#xff09; 分享 | Java中文社群#xff08;ID#xff1a;javacn666#xff09;前言 递归#xff0c;是一个非常重要的概念#xff0c;也是面试中非常喜欢考的。因为它不但能考察… 这是磊哥的第 189 期分享作者 | 田小齐来源 | 码农田小齐IDNYCSDE 分享 | Java中文社群IDjavacn666前言 递归是一个非常重要的概念也是面试中非常喜欢考的。因为它不但能考察一个程序员的算法功底还能很好的考察对时间空间复杂度的理解和分析。本文只讲一题也是几乎所有算法书讲递归的第一题但力争讲出花来在这里分享四点不一样的角度让你有不同的收获。时空复杂度的详细分析识别并简化递归过程中的重复运算披上羊皮的狼适当炫技助我拿到第一份工作算法思路 大家都知道一个方法自己调用自己就是递归没错但这只是对递归最表层的理解。那么递归的实质是什么答递归的实质是能够把一个大问题分解成比它小点的问题然后我们拿到了小问题的解就可以用小问题的解去构造大问题的解。那小问题的解是如何得到的答用再小一号的问题的解构造出来的小到不能再小的时候就是到了零号问题的时候也就是 base case 了。那么总结一下递归的三个步骤Base case就是递归的零号问题也是递归的终点走到最小的那个问题能够直接给出结果不必再往下走了否则就会成死循环拆解每一层的问题都要比上一层的小不断缩小问题的 size才能从大到小到 base case组合得到了小问题的解还要知道如何才能构造出大问题的解。所以每道递归题我们按照这三个步骤来分析把这三个问题搞清楚代码就很容易写了。斐波那契数列 这题虽是老生常谈了但相信我这里分享的一定会让你有其他收获。题目描述斐波那契数列是一位意大利的数学家他闲着没事去研究兔子繁殖的过程研究着就发现可以写成这么一个序列1123581321… 也就是每个数等于它前两个数之和。那么给你第 n 个数问 F(n) 是多少。解析用数学公式表示很简单代码也很简单用我们刚总结的三步base case: f(0) 0, f(1) 1.分解f(n-1), f(n-2)组合f(n) f(n-1) f(n-2)那么写出来就是class Solution {public int fib(int N) {if (N 0) {return 0;} else if (N 1) {return 1;}return fib(N-1) fib(N-2);}
}
但是这种解法 Leetcode 给出的速度经验只比 15% 的答案快因为它的时间复杂度实在是太高了过程分析那这就是我想分享的第一点如何去分析递归的过程。首先我们把这颗 Recursion Tree 画出来比如我们把 F(5) 的递归树画出来那实际的执行路线是怎样的首先是沿着最左边这条线一路到底F(5) → F(4) → F(3) → F(2) → F(1)好了终于有个 base case 可以返回 F(1) 1 了然后返回到 F(2) 这一层再往下走就是 F(0)又触底反弹回到 F(2)得到 F(2) 10 1 的结果把这个结果返回给 F(3)然后再到 F(1)拿到结果后再返回 F(3) 得到 F(3) 左 右 2再把这个结果返上去...这种方式本质上是由我们计算机的冯诺伊曼体系造就的目前一个 CPU 一个核在某一时间只能执行一条指令所以不能 F(3) 和 F(4) 一起进行了一定是先执行了 F(4) 本代码把 fib(N-1) 放在前面再去执行 F(3).我们在 IDE 里 debug 就可以看到栈里面的情况这里确实是先走的最左边这条线路一共有 5 层然后再一层层往上返回。没看懂的小伙伴可以看视频讲解哦时间复杂度分析如何评价一个算法的好坏很多问题都有多种解法毕竟条条大路通罗马。但如何评价每种方法的优劣我们一般是用大 O 表达式来衡量时间和空间复杂度。时间复杂度随着自变量的增长算法所需时间的增长情况。这里大 O 表示的是一个算法在 worst case 的表现情况这就是我们最关心的不然春运抢车票的时候系统 hold 不住了你跟我说这个算法很优秀当然还有其他衡量时间和空间的方式比如Theta: 描述的是 tight boundOmega(n): 这个描述的是 best case最好的情况没啥意义这也给我们了些许启发不要说你平时表现有多好没有意义面试衡量的是你在 worst case 的水平不要说面试没有发挥出你的真实水平扎心的是那就是我们的真实水平。那对于这个题来说时间复杂度是多少呢答因为我们每个节点都走了一遍所以是把所有节点的时间加起来就是总的时间。在这里我们在每个节点上做的事情就是相加求和是 O(1) 的操作且每个节点的时间都是一样的所以总时间 节点个数 * 每个节点的时间那就变成了求节点个数的数学题在 N 5 时最上面一层有1个节点第二层 2 个第三层 4 个第四层 8 个第五层 16 个如果填满的话想象成一颗很大的树:)这里就不要在意这个没填满的地方了肯定是会有差这么几个 node但是大 O 表达的时间复杂度我们刚说过了求的是 worst case.那么总的节点数就是1 2 4 8 16这就是一个等比数列求和了当然你可以用数学公式来算但还有个小技巧可以帮助你快速计算其实前面每一层的节点相加起来的个数都不会超过最后一层的节点的个数总的节点数最多也就是最后一层节点数 * 2然后在大 O 的时间复杂度里面常数项也是无所谓的所以这个总的时间复杂度就是最后一层节点的个数2^n没看懂别慌去 B 站/油管看我的视频讲解哦搜「田小齐」就好了。空间复杂度分析一般书上写的空间复杂度是指算法运行期间所需占用的所有内存空间但是在公司里大家常用的也是面试时问的指的是Auxiliary space complexity运行算法时所需占用的额外空间。举例说明区别比如结果让你输出一个长度为 n 的数组那么这 O(n) 的空间是不算在算法的空间复杂度里的因为这个空间是跑不掉的不是取决于你的算法的。那空间复杂度怎么分析呢我们刚刚说到了冯诺伊曼体系从图中也很容易看出来是最左边这条路线占用 stack 的空间最多一直不断的压栈也就是从 5 到 4 到 3 到 2 一直压到 1才到 base case 返回每个节点占用的空间复杂度是 O(1)所以加起来总的空间复杂度就是 O(n).我在上面????的视频里也提到了不懂的同学往上翻看视频哦优化算法那我们就想了为什么这么一个简简单单的运算竟然要指数级的时间复杂度到底是为什么让时间如此之大。那也不难看出来在这棵 Recursion Tree 里有太多的重复计算了。比如一个 F(2) 在这里都被计算了 3 次F(3) 被计算了 2 次每次还都要再重新算这不就是狗熊掰棒子吗真的是一把辛酸泪。那找到了原因之后为了解决这种重复计算计算机采用的方法其实和我们人类是一样的记笔记。对很多职业来说比如医生、律师、以及我们工程师为什么越老经验值钱因为我们见得多积累的多下次再遇到类似的问题时能够很快的给出解决方案哪怕一时解决不了也避免了一些盲目的试错我们会站在过去的高度不断进步而不是每次都从零开始。回到优化算法上来那计算机如何记笔记呢我们要想求 F(n)无非也就是要记录 F(0) ~ F(n-1) 的值那选取一个合适的数据结构来存储就好了。那这里很明显了可以用一个数组来存Index012345F(n)011235那有了这个 cheat sheet我们就可以从前到后得到结果了这样每一个点就只算了一遍用一个 for loop 就可以写出来代码也非常简单。class Solution {public int fib(int N) {if (N 0) {return 0;}if (N 1) {return 1;}int[] notes new int[N1];notes[0] 0;notes[1] 1;for(int i 2; i N; i) {notes[i] notes[i-1] notes[i-2];}return notes[N];}
}
这个速度就是 100% 了但是我们可以看到空间应该还有优化的余地。那仔细想想其实我们记笔记的时候需要记录这么多吗需要从幼儿园到小学到初中到高中的笔记都留着吗那其实每项的计算只取决于它前面的两项所以只用保留这两个就好了。那我们可以用一个长度为 2 的数组来计算或者就用 2 个变量。更新代码class Solution {public int fib(int N) {int a 0;int b 1;if(N 0) {return a;}if(N 1) {return b;}for(int i 2; i N; i) {int tmp a b;a b;b tmp;}return b;}
}
这样我们就把空间复杂度优化到了 O(1)时间复杂度和用数组记录一样都是 O(n).这种方法其实就是动态规划 Dynamic Programming写出来的代码非常简单。那我们比较一下 Recursion 和 DPRecursion 是从大到小层层分解直到 base case 分解不了了再组合返回上去DP 是从小到大记好笔记不断进步。也就是 Recursion Cache DP如何记录这个笔记如何高效的记笔记这是 DP 的难点。有人说 DP 是拿空间换时间但我不这么认为这道题就是一个很好的例证。在用递归解题时我们可以看到空间是 O(n) 在栈上的但是用 DP 我们可以把空间优化到 O(1)DP 可以做到时间空间的双重优化。其实呢斐波那契数列在现实生活中也有很多应用。比如在我司以及很多大公司里每个任务要给分值1分表示大概需要花1天时间完成然后分值只有12358这5种如果有大于8分的任务就需要把它 break down 成8分以内的以便大家在两周内能完成。因为任务是永远做不完的而每个人的时间是有限的所以每次小组会开会挑出最重要的任务让大家来做然后每个人根据自己的 available 的天数去 pick up 相应的任务。披着羊皮的狼 那有同学可能会想这题这么简单这都 2020 年了面试还会考么答真的会。只是不能以这么直白的方式给你了。比如很有名的爬楼梯问题一个 N 阶的楼梯每次能走一层或者两层问一共有多少种走法。这个题这么想站在当前位置只能是从前一层或者前两层上来的所以 f(n) f(n-1) f(n-2).这题是我当年面试时真实被问的那时我还在写 python为了炫技还用了lambda function:f lambda n: 1 if n in (1, 2) else f(n-1) f(n-2)
递归的写法时间复杂度太高所以又写了一个 for loop 的版本def fib(n)a, b 1, 1for i in range(n-1):a, b b, abreturn a
然后还写了个 caching 的方法:def cache(f):memo {}def helper(x):if x not in memo:memo[x] f(x)return memo[x]return helper
cache
def fibR(n):if n1 or n2: return 1return fibR(n-1) fibR(n-2)
还顺便和面试官聊了下 tail recursion:tail recursion 尾递归就是递归的这句话是整个方法的最后一句话。那这个有什么特别之处呢尾递归的特点就是我们可以很容易的把它转成 iterative 的写法当然有些智能的编译器会自动帮我们做了不是说显性的转化而是在运行时按照 iterative 的方式去运行实际消耗的空间是 O(1)那为什么呢因为回来的时候不需要 backtrack递归这里就是最后一步了不需要再往上一层返值。def fib(n, a0, b1):if n0: return aif n1: return breturn fib(n-1, b, ab)
最终拿出了我的杀手锏lambda and reducefibRe lambda n: reduce(lambda x, n: [x[1], x[0]x[1]], range(n), [0, 1])
看到面试官满意的表情后就开始继续深入的聊了...所以说不要以为它简单同一道题可以用七八种方法来解分析好每个方法的优缺点引申到你可以引申的地方展示自己扎实的基本功这场面试其实就是你 show off 的机会lol如果大家喜欢这种形式请素质三连点击在看鼓励下我瞎写点评论假装我很红转发给「需要」的人即使他不需要if快还是switch快解密switch背后的秘密一道题决定去留为什么synchronized无法禁止指令重排却能保证有序性关注公众号发送”进群“老王拉你进读者群。
