作者:白日做梦家_ | 来源:互联网 | 2023-01-26 20:45
对于经典的裴波拉契数列:f(n) = f(n-1)+f(n-2), f(0) = 0, f(1) = 1.(抱歉现在markdown里面插入latex公式还不会,后面再补咯)。
直接用递归实现,可以发现,当求f(n-1)时,需要从f(2)到f(n-2)的每一项值,求f(n-2)时需要f(2)到f(n-3)的每一项值,这中间包含了很多的重复,算法复杂度用树来分析,基本是一个满二叉树的节点数目,即O(2^n)。
如何简化算法复杂度的问题,可以用长度为N的数组存储计算过的值,采用从2到N递推计算的方式,这种方法空间复杂度为O(N), 时间复杂度为O(N).采用求解系数矩阵,直接将[f(n) f(n-1)] 与[f(1) f(0)]联系起来,这样只要求矩阵方幂,并对N进行二进制分解,可将时间复杂度将至O(logN)。
我们对递归方法进行一下优化,可以实现O(N)的时间复杂度,方法就是转化为尾递归:
int fibonacci(int n, int a, int b){
if(n == 0) return b;
else {
return fibonacci(n-1, b, a + b);
}
}
fibonacci(5, 0, 1);
这里实际上是将原来用两项f(n) 和 f(n-1)计算的结果放到了一个局部变量a+b中,并且由于该递归为尾递归,即递归部分是最后一步,可以实现原地递归:尾递归优化,不需要对先前的递归调用保留栈帧。这样就可以实现常数空间复杂度。
- 尾递归来自于更加普通的尾调用:即对某函数的当前函数的最后一步,因此我们可以不用保存当前函数的局部变量,直接进入被调用的函数,因此实现尾调用优化,当函数在最后一步递归调用自身时,就是尾递归。