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

Question

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

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

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

主方法在这里不适用，我无法猜测使用替换方法（我反正不想使用替换方法）。我只剩下递归树方法了。

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

我知道我必须找到树中的节点数，其中每个节点 ( k) 为其子节点的所有节点编号从 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)