首页 > 代码库 > 递归算法时间复杂度分析与改善
递归算法时间复杂度分析与改善
递归算法大家都不陌生，当须要反复计算同样问题时，一般能够选择递归和循环两种算法。
又由于递归实现起来代码比較简洁。所以通常都会使用递归来解决上述问题。比方斐波那契数列。再比方树的前序、中序、兴许遍历算法。
递归算法尽管是有代码简洁这个长处，可是其缺点显著。
由于递归函数是在运行过程中调用其自身，所以会占用大量的栈上空间，而且压栈和出栈都是有时间消耗的。
所以从这一点上来看，递归的效率是不如循环。除了效率之外，递归另一个相当明显的问题：可能会导致栈溢出。当递归调用的次数过大时，非常有可能会出现栈溢出的情况。
我们这里暂不考虑空间复杂度，仅讨论其时间复杂度以及改善方法。
还是以经典的Fibonacci数列为例。其定义例如以下：
1. 递归解法
对于这个题目，大家对于其算法已经十分熟悉。非常快就能写出以下的代码：
long long Fibonacci(unsigned int n)
{
if (n <= 0) {
return 0;
}
if (n == 1) {
return 1;
}
return Fibonacci(n-1) + Fibonacci(n-2);
}我们以f(10)为例分析来分析递归的计算过程。f(10)=f(9)+f(8), f(9)=f(8)+f(7), f(8)=f(7)+f(6)。。。。
能够用树形结构来表示整个计算过程
我们能够看出来，上面的树中，非常多结点都是反复计算的。其实，递归算法的时间复杂度是n的指数级的。这种复杂度。一般来说是不可接受的。
2. 递归算法改善
上述的递归算法中。时间复杂度高的原因是过程中存在大量的反复计算。因此，假设能想办法避免反复计算，那么其时间复杂度便能够降下来。
比較简单的方法是採用逆序的递归算法：f(0)+f(1)=f(2), f(1)+f(2)=f(3)，以此类推便能够计算出f(n)。
而且这个算法的时间复杂度非常明显，就是O(n)。代码例如以下：
long long Fibonacci(unsigned int n)
{
long long fibNMinusOne = 1;
long long fibNMinusTwo = 0;
long long fibN = 0;
int result[2] = {0, 1};
int i;
if (n < 2) {
return result[n];
}
for (i = 2; i < n; i++) {
fibN = fibNMinusTwo + fibNMinusOne;
fibNMinusTwo = fibNMinusOne;
fibNMinusOne = fibN;
}
return fibN;
}递归算法时间复杂度分析与改善
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。