如何用递归树求解 T(n) = T(n-1) + n^2
How to solve T(n) = T(n-1) + n^2 with recursion tree
我在用递归树解决这个 T(n)=T(n-1)+n^2 问题时遇到了问题，谁能帮我发张图片让我更容易理解？
谢谢
只需展开等式：
&space;=&space;T(n-1)&space;+&space;n%5E2&space;=&space;(T(n-2)&space;+&space;(n-1)%5E2)&space;+&space;n%5E2 "T(n) = T(n-1) + n^2 = (T(n-2) + (n-1)^2) + n^2")
利用数学归纳法，你可以写出如果
=1 "T(1)=1")
&space;=&space;1&space;+&space;2%5E2&space;+&space;3%5E2&space;+&space;...&space;+&space;n%5E2&space;=&space;%5Cfrac%7Bn(n+1)(2n+1)%7D%7B6%7D&space;=&space;%5CTheta(n%5E3). "T(n) = 1 + 2^2 + 3^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6} = \Theta(n^3)")
我在用递归树解决这个 T(n)=T(n-1)+n^2 问题时遇到了问题，谁能帮我发张图片让我更容易理解？ 谢谢
只需展开等式：
利用数学归纳法，你可以写出如果