如何解决递归T(n)= T(n-1)+ ... T(1)+1?

蝙蝠侠

我需要找到涉及递归的算法的复杂性:

T(n) = T(n-1) + ... + T(1) + 1

T(n)是解决尺寸问题所需要的时间n

主方法不适用于此处,我无法猜测使用替代方法(无论如何我都不想使用替代方法)。我剩下的是递归树方法。

由于每个节点的子节点数量不是一个常数,因此我很难跟踪每个节点的贡献量。潜在的模式是什么?

我知道我必须找到树中的节点数,其中每个节点(k)的子节点都有从1到编号的所有节点k-1

T(n)给定该公式也可以找到确切的时间吗?

鉴于

自从 T(n-1) = T(n-2) + ... + T(1) + 1

T(n) = T(n-1) + T(n-2) + ... + T(1) + 1
     = T(n-1) + T(n-1)
     = 2*T(n-1)

T(1) = 1=>T(n) = 2^(n-1)

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

如何解决该递归T(n)= T(n − 1)+ lg(1 + 1 / n),T(1)= 1?

如何解决递归T(n)= T(n / 2)+ T(n / 4),T(1)= 0,T(2)= 1是T(n)=Θ(n lgφ),哪里是黄金分割率?

计算递归关系T(n)= T(n / log n)+Θ(1)

T(0) = 1, T(1) = 0, T(n ) = 2* T(n-2) 的递归关系

如何递归求解T(n)= 5T(n / 2)+ n ^ 2,T(1)= 2

您能帮我解决递归关系T(1)= 5,并且对于所有n> = 2,T(n)= 2T(n-1)+(3 * n + 1)

如何用递归树求解 T(n) = T(n-1) + n^2

求解递归关系:T(n)= T(n-1)+ n-1

求解递归关系:T(n)= T(n-1)+ T(n / 2)+ n

与主定理T(n)= T(n ^(1/2))+ 1有关的递归

如何求解T(n)= T(0.2 * n ^ 0.5)+ 1?

如何使用递归树求解方程T(n)= 5T(n / 5)+ sqrt(n),T(1)= 1,T(0)= 0?

求解:T(n)= T(n / 2)+ n / 2 +1

T(N)= 2T(N − 1)+ N,T(1)= 2的Big-O

递归T(n)= 2T(n-1)+ 1给出的递归算法的时间复杂度是多少

求解递归T(floor [n / 2])+ T(ceil [n / 2])+ n-1

计算递归关系T(n)= T(n / [(log n)^ 2])+Θ(1)

递归 T(n)= 2T(n-1) + (2^n)

递归关系的时间复杂度:T(n) = nT(n^1/2)+ O(1)

T(n)> = T(n-1)始终为真吗?

递归的复杂度T(n)= T(n-2)+ 1 / lgn?

T(n) 的时间复杂度 = T(n - 1) + (n - 1)^2

如何解决休眠n + 1问题OneToMany和ManyToOne

我该如何解决N + 1选择问题?

[-t 1]检查什么?

T -SQL PATINDEX -1

对于6 T(1)= 1的n次幂,计算机科学数学中的递归关系T(n)= 6T(n / 6)+ 2n + 3?

关系的时间复杂度T(n)= T(n-1)+ T(n / 2)+ n

为什么我在返回F(n-1,t)+ F(n,t-1)行时出错?