问题描述
我想了解如何得出以下递归关系的复杂性。
I want to understand how to arrive at the complexity of the below recurrence relation.
T（n）= T（n-1 ）+ T（n-2）+ C
给定 T（1）= C 和 T（ 2）= 2C;
通常用于 T（n）= 2T（n / 2）+ C （给出T（1）= C），我使用以下方法。
Generally for equations like T(n) = 2T(n/2) + C (Given T(1) = C), I use the following method.
T(n) = 2T(n/2) + C
=> T(n) = 4T(n/4) + 3C
=> T(n) = 8T(n/8) + 7C
=> ...
=> T(n) = 2^k T (n/2^k) + (2^k - 1) c
现在当 n / 2 ^ k = 1 => K =对数（n）（以2为底）
T(n) = n T(1) + (n-1)C
= (2n -1) C
= O(n)
但是，对于我所遇到的问题，我无法提出类似的方法。如果我的方法不正确，请纠正我。
But, I'm not able to come up with similar approach for the problem I have in question. Please correct me if my approach is incorrect.
推荐答案
复杂度与输入大小有关，其中每次调用都会产生一个二进制代码，通话树
The complexity is related to input-size, where each call produce a binary-tree of calls
其中 T（n）使 2 总共..
Where T(n) make 2 calls in total ..
T（ n）= T（n-1）+ T（n-2）+ C
T（n） = O（2 ）+ O（2 ）+ O（1）
O（2 ）
您可以用相同的方式将递归函数推广为斐波那契数
In the same fashion, you can generalize your recursive function, as a Fibonacci number
T（n）= F（n）+（C * 2 ）
接下来，您可以使用直接公式代替递归方式
Next you can use a direct formula instead of recursive way
使用称为
这篇关于递归的复杂度：T（n）= T（n-1）+ T（n-2）+ C的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！