递归的复杂度：T（n）= T（n-1）+ T（n-2）+ C [英] Complexity of the recursion: T(n) = T(n-1) + T(n-2) + C

问题描述

我想了解如何得出以下递归关系的复杂性。

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 n 总共..

Where T(n) make 2n calls in total ..

T（ n）= T（n-1）+ T（n-2）+ C

T（n） = O（2 n-1 ）+ O（2 n-2 ）+ O（1）

O（2 n ）

您可以用相同的方式将递归函数推广为斐波那契数

In the same fashion, you can generalize your recursive function, as a Fibonacci number

T（n）= F（n）+（C * 2 n ）

接下来，您可以使用直接公式代替递归方式

Next you can use a direct formula instead of recursive way

使用称为 Binet的公式

这篇关于递归的复杂度：T（n）= T（n-1）+ T（n-2）+ C的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！