我看了一个证明T(n)= T(n-1) + n is O(n^2)的视频
我有以下表达式：
T(1) = 4
T(N) = T(N – 1) + N + 3, N > 1
我的问题是，即使N之后有+3，上面的表达式是否也以相同的方式解决了？
这个问题有点混乱，但是我希望你明白这一点。如果有问题，我会尽力解释。
总之，T（N）= T（N – 1）+ N + 3 = O（n ^ 2）
T（n）= T（n-1）+ n-1 + 4
T（n）= T（n-1）+ n-1 + T（1）...（1）
现在，T（1）=常数。
因此，从eq（1），
T（n）= T（n-1）+（n-1）...（2）
Eq（2）简化为T（n）= T（n-k）+ n k-k（k + 1）/ 2 ...（3）
在等式（3）中替换（n-k）= 1或k =（n-1）时，
我们得到]
T（n）= T（1）+ n *（n-1）-（n-1）（n）/ 2
T（n）= n *（n-1）/ 2 => O（n ^ 2）