algorithm - 使用主方法解决复发

Question

我正在尝试解决递归关系以找出我编写的算法的复杂性。这是等式。。

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

我找到了 O(n2) 的答案，但我不确定我是否做对了。有人可以确认吗？

更新：如果方程是 T(n) = T(n-1)+Θ(nlogn) 怎么办？它仍然是O（n2）吗？

Answer 1

它是 O(N)+O(N-1)+...+O(1) = O(N*(N+1)/2)。所以是的，总复杂度是二次的。

Answer 2

是的，你猜对了。

但是，递归的形式不适合 Master 方法。既然你已经猜对了界限，那么替换方法在这里更合适。

现在你的工作是找到两个常数c并n0证明：

T(n) <= c*(n^2)对全部n >= n0