正如标题所言,在我四年的编程经历中就没刷过一道算法题,这可能与我所编写的应用有关,算法对我而言提升不是特别大。加上我几乎都是在需求中学习,而非系统性的学习。所以像算法这种基础知识我自然就不是很熟悉。
那我为何会接触算法呢?
我在今年暑假期间有一个面试,当时面试官想考察一下我的算法能力,而我直接明摆了和说我不行(指算法上的不行),但面试官还是想考察一下,于是就出了道斐波那契数列作为考题。
但我毕竟也接触了 4 年的代码,虽然不刷算法,但好歹也看过许多文章和代码,斐波那契数列使用递归实现的代码也有些印象,于是很快我就写出了下面的代码作为我的答案。
function fib(n) {
if (n <= 1) return n
return fib(n - 1) + fib(n - 2)
}
面试官问我还有没有更好的答案,我便摇了摇头表示这 5 行不到的代码难道不是最优解?
事实上这份代码看起来很简洁,实际却是耗时最慢的解法
毫无疑问,在算法这关我肯定是挂了的,不过好在项目经验及后续的项目实践考核较为顺利,不然结局就是回去等通知了。最后面试接近尾声时,面试官友情提醒我加强基础知识(算法),强调各种应用框架不断更新迭代,但计算机的底层基础知识是不变的。于是在面试官的建议下,便有了本文。
好吧,我承认我是为了面试才去学算法的。
对上述代码进行优化
在介绍我是从何处学习算法以及从中学到了什么,不妨先来看看上题的最优答案是什么。
对于有接触过算法的同学而言,不难看出时间复杂度为 O(n²),而指数阶属于爆炸式增长,当 n 非常大时执行效果缓慢,且可能会出现函数调用堆栈溢出。
如果仔细观察一下,会发现这其中进行了非常多的重复计算,我们不妨将设置一个 res 变量来输出一下结果
function fib(n) {
if (n <= 1) {
return n
}
const res = fib(n - 1) + fib(n - 2)
console.log(res)
return res
}
当 n=7 时,所输出的结果如下
这还只是在 n=7 的情况下,便有这么多输出结果。而在算法中要避免的就是重复计算,这能够高效的节省执行时间,因此不妨定义一个缓存变量,在递归时将缓存变量也传递进去,如果缓存变量中存在则说明已计算过,直接返回结果即可。
function fib(n, mem = []) {
if (n <= 1) {
return n
}
if (mem[n]) {
return mem[n]
}
const res = fib(n - 1, mem) + fib(n - 2, mem)
console.log(res)
mem[n] = res
return res
}