吊打面试官系列:你会「递归」么?
The following article is from 码农田小齐 Author 小齐本齐
递归,是一个非常重要的概念,也是面试中非常喜欢考的。因为它不但能考察一个程序员的算法功底,还能很好的考察对时间空间复杂度的理解和分析。
本文只讲一题,也是几乎所有算法书讲递归的第一题,但力争讲出花来,在这里分享四点不一样的角度,让你有不同的收获。
时空复杂度的详细分析
识别并简化递归过程中的重复运算
披上羊皮的狼
算法思路
大家都知道,一个方法自己调用自己就是递归,没错,但这只是对递归最表层的理解。
那么递归的实质是什么?
答:递归的实质是能够把一个大问题分解成比它小点的问题,然后我们拿到了小问题的解,就可以用小问题的解去构造大问题的解。
那小问题的解是如何得到的?
答:用再小一号的问题的解构造出来的,小到不能再小的时候就是到了零号问题的时候,也就是 base case 了。
那么总结一下递归的三个步骤:
Base case:就是递归的零号问题,也是递归的终点,走到最小的那个问题,能够直接给出结果,不必再往下走了,否则,就会成死循环;
拆解:每一层的问题都要比上一层的小,不断缩小问题的 size,才能从大到小到 base case;
组合:得到了小问题的解,还要知道如何才能构造出大问题的解。
所以每道递归题,我们按照这三个步骤来分析,把这三个问题搞清楚,代码就很容易写了。
斐波那契数列
这题虽是老生常谈了,但相信我这里分享的一定会让你有其他收获。
题目描述
斐波那契数列是一位意大利的数学家,他闲着没事去研究兔子繁殖的过程,研究着就发现,可以写成这么一个序列:1,1,2,3,5,8,13,21… 也就是每个数等于它前两个数之和。那么给你第 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)
public int fib(int N) {
if (N == 0) {
return 0;
} else if (N == 1) {
return 1;
}
return fib(N-1) + fib(N-2);
}
}
过程分析
时间复杂度分析
如何评价一个算法的好坏?
时间复杂度:随着自变量的增长,算法所需时间的增长情况。
Theta: 描述的是 tight bound
Omega(n): 这个描述的是 best case,最好的情况,没啥意义
那对于这个题来说,时间复杂度是多少呢?
第二层 2 个,
第三层 4 个,
第四层 8 个,
第五层 16 个,如果填满的话,想象成一颗很大的树:)
1 + 2 + 4 + 8 + 16
空间复杂度分析
算法运行期间所需占用的所有内存空间
Auxiliary space complexity:
运行算法时所需占用的额外空间。
优化算法
记录 F(0) ~ F(n-1) 的值,
那选取一个合适的数据结构来存储就好了。
public int fib(int N) {
if (N == 0) {
return 0;
}
if (N== 1) {
return 1;
}
int[] notes = new int[N+1];
notes[0] = 0;
notes[1] = 1;
for(int i = 2; i <= N; i++) {
notes[i] = notes[i-1] + notes[i-2];
}
return notes[N];
}
}
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;
}
}
Recursion 是从大到小,层层分解,直到 base case 分解不了了再组合返回上去;
DP 是从小到大,记好笔记,不断进步。
也就是 Recursion + Cache = DP
比如在我司以及很多大公司里,每个任务要给分值,1分表示大概需要花1天时间完成,然后分值只有1,2,3,5,8这5种,(如果有大于8分的任务,就需要把它 break down 成8分以内的,以便大家在两周内能完成。)
因为任务是永远做不完的而每个人的时间是有限的,所以每次小组会开会,挑出最重要的任务让大家来做,然后每个人根据自己的 available 的天数去 pick up 相应的任务。
披着羊皮的狼
一个 N 阶的楼梯,每次能走一层或者两层,问一共有多少种走法。
a, b = 1, 1
for i in range(n-1):
a, b = b, a+b
return a
memo = {}
def helper(x):
if x not in memo:
memo[x] = f(x)
return memo[x]
return helper
@cache
def fibR(n):
if n==1 or n==2: return 1
return fibR(n-1) + fibR(n-2)
tail recursion 尾递归:就是递归的这句话是整个方法的最后一句话。
尾递归的特点就是我们可以很容易的把它转成 iterative 的写法,当然有些智能的编译器会自动帮我们做了(不是说显性的转化,而是在运行时按照 iterative 的方式去运行,实际消耗的空间是 O(1))
因为回来的时候不需要 backtrack,递归这里就是最后一步了,不需要再往上一层返值。
if n==0: return a
if n==1: return b
return fib(n-1, b, a+b)
新勋章,新奖品,高流量,还有更多福利等你来拿
更多精彩推荐
☞用 Python 实现手机自动答题,下一个百万获奖人可能就是你!
☞用 Python 实现手机自动答题,这下百万答题游戏谁也玩不过我!
☞IDEA 惊天 bug:进程已结束,退出代码 1073741819