C++怎么根据递推公式求时间复杂度？
如题目：
设某算法的时间复杂度函数的递推方程是T(n)=T(n−1)+n（为正整数）及T(0)=1，则该算法的时间复杂度为（ ）。
为什么答案是O(n^2) ？我想知道解题过程。
以下回答参考GPT并且由Bony-整理：
要根据递推公式求时间复杂度，可以使用主定理（Master Theorem）或代入法（Substitution Method）等数学方法。对于该题目，我们可以使用代入法来求解。
首先，根据递推公式，可以得到：
T(n) = T(n-1) + n
= T(n-2) + (n-1) + n
= T(n-3) + (n-2) + (n-1) + n
= ...
= T(0) + 1 + 2 + 3 + ... + n
其中，T(0) = 1。
接下来，我们需要求出上式中求和部分的时间复杂度。可以使用等差数列求和公式，得到：
1 + 2 + 3 + ... + n = (n^2 + n) / 2
因此，递推公式的时间复杂度为：
T(n) = T(0) + (n^2 + n) / 2
= 1 + (n^2 + n) / 2
= O(n^2)
因此，该算法的时间复杂度为 O(n^2)。
需要注意的是，在使用代入法时，需要猜测递推公式的时间复杂度，并通过数学归纳法证明猜测的时间复杂度是正确的。