有人可以帮我解决这个问题吗?
Use iteration method to solve it. T(n) = T(n-1) +n
将不胜感激步骤说明。
最佳答案
T(n) = T(n-1) + n
T(n-1) = T(n-2) + n-1
T(n-2) = T(n-3) + n-2
依此类推,您可以将 T(n-1) 和 T(n-2) 的值替换为 T(n) 以获得该模式的一般概念。
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 ...(1)
对于基本情况:
n - k = 1 so we can get T(1)
=> k = n - 1
代入 (1)
T(n) = T(1) + (n-1)n - (n-1)(n-2)/2
你可以看到它是 n2 => O(n2) 阶的。
关于algorithm - 简单 : Solve T(n)=T(n-1)+n by Iteration Method,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13674719/