暴力递归
斐波那契数列的数学形式就是递归,直接上代码:
public static int fibonacci(int n) {
if (n <= 2) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
根据斐波那契数列的特性,我们画出他的递归树:
根据递归树,可以看出,要计算f(20)就得计算出f(19)+f(18),以此类推。遇到f(1),f(2)结果已知,这样递归树不再增长,可以直接返回结果。
递归的时间复杂度
时间复杂度=子问题的个数乘以解决一个子问题需要的时间。
递归树中节点的个数为 二叉树的节点,即2n+1 次方减1(n为树的高度),指数级别,所以求子问题的时间复杂度为O(2n).
在斐波那契的暴力递归中,解决子问题的时间没有循环,故时间复杂度为O(1).
最终得时间复杂度为出O(1)*O(2n)=O(2n)
但是根据递归树可以看出,f(18)被计算了两次,诸如此类,有很多大量的重复的计算,消耗时间,低效,就是动态规划的第一个性质重叠子问题。
带备忘录的递归算法
备忘录就是我们把重复的计算结果存储到备忘录里,遇到之后直接查出来,不再去计算(递归)一遍,一般可以用一个数组或者其他集合充当备忘录。
上代码:
public static int fibonacciMemo(List<Integer> memo, int n) {
if (n <= 2) {
return 1;
}
if (memo.get(n) != 0) {
return memo.get(n);
}
memo.add(n, fibonacciMemo(memo, n - 1) + fibonacciMemo(memo, n - 2));
return memo.get(n);
}
加了备忘录的递归树:
带备忘录的递归算法就是把一颗巨大冗余的递归树通过剪裁,改造成了不冗余的递归图,减少子问题的解决
自顶向下
带备忘录的递归算法时间复杂度
根据时间复杂的公式:
子问题的求解时间复杂度等于 O(1)。
由于改造后不涉及冗余计算子问题的数量变成了线形的,为O(n).
最后的时间复杂度也为O(n).
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)