问求解递推T(n) =T(n-1)+T(n-2)+T(n-3)+.+ T(1)

EN

这里有一个简单的方法:您可以通过扩展每个附加项并观察模式来计算时间复杂度：

T(n)

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

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

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

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

= 2^(k-1) T()+.+ 2^(k-1) T(1)

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

= 2^(n-2)

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

因此，T(n) = c * 2^n，其中c是T(1)/2。

你有以下几点：

T(1) = 1
T(2) = T(2-1) = T(1) = 1
T(3) = T(3-1) + T(3-2) = T(2) + T(1) = 2
T(4) = T(4-1) + T(4-2) + T(4-3) = T(3) + T(2) + T(1) = 2 + 1 + 1 = 4
T(5) = 4 + 2 + 1 + 1 = 8
T(6) = 8 + 4 + 2 + 1 + 1 = 16
...

通过归纳，得出了T(n) = 2*T(n-1)与大小写T(1) = T(2) = 1的关系。

我们可以在这句话的基础上更进一步，因为T(n) = 2*T(n-1)，T(n) = 2*2*T(n-2)。因此，T(n) = (2^i)*T(n-i)用于i < n-2和n > 2。

因此，就时间复杂度而言，我们得到了O(2^n)。

注意:如果我错了，请纠正我。我对这些东西不是最好的。我的预言片。我在努力学习自己。