容易:通过迭代法求解T(n)= T(n-1)+ n

Question

有人可以帮我这个吗？

使用迭代方法来解决它. T(n)= T(n-1)+ n

非常感谢步骤的解释.

Answer 1

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

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

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

等等,你可以用T(n)中的T(n-1)和T(n-2)的值来代替模式的一般概念.

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


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

T(n) = T(n-k) +kn - k(k-1)/2

对于基本情况:

n - k =1 so we can get T(1)

k = n - 1替代上面

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

您可以看到订单n ^ 2

Answer 2

扩大它!

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

等等,直到

T(n) = 1 + 2 + ... + n = n(n+1)/2   [= O(n^2)]

提供的 T(1) = 1