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

Question

我需要找到涉及重现的算法的复杂性:

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

T(n)是解决大小问题所需的时间n.

master方法在这里不适用,我不能猜测使用替换方法(我不想使用替换方法).我留下了递归树方法.

由于每个节点的子节点数不是常数,我发现很难跟踪每个节点的贡献.底层模式是什么？

我知道我必须在树中找到节点的数量,其中每个节点(k)为其子节点具有从1到1的所有节点k-1.

是否也可以找到T(n)给定公式的确切时间？

Answer 1

以来 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)