NOIP 普及组初赛 · NOIP 2015 普及组初赛试题 第 19 题

某算法的计算时间表示为递推关系式 $T(n)=T(n-1)+n$（$n$ 为正整数）及 $T(0)=1$，则该算法的时间复杂度为( )。

这题就是让你把递推式一步步‘剥洋葱’，一直剥到最底层的 T(0)，你会发现它其实就是一个从 1 加到 n 的求和公式，主导项是 n²，所以选 D。

很多同学看到 T(n)=T(n-1)+n 就以为每次只加一个 n，直接选 O(n)，这是典型的‘只看表面不看本质’。递推式里的 +n 是随着 n 变化的，每次加的数都比上一次多 1，展开后是一堆数相加，不是单个数重复加。还有人选 O(n log n) 是因为脑子里蹦出‘递推+对数’的刻板印象，或者混淆了二分查找的复杂度，但这里根本没有二分或分治结构。务必记住：递推展开后是等差数列求和，公式是 n(n+1)/2，量级就是 n²。

这道题考什么

题目给的是一个简单的递推式 $T(n)=T(n-1)+n$，还给了初始条件 $T(0)=1$。它问的是时间复杂度，也就是 $T(n)$ 随着 $n$ 变大时的增长量级。

知识点：递推展开与求和

这类题的核心就是递推展开：把 $T(n)$ 写成 $T(n-1)$ 的形式，再把 $T(n-1)$ 展开成 $T(n-2)$，一直往下推，直到推到最底层的 $T(0)$。

展开的过程是这样的： $$\begin{aligned} T(n) &= T(n-1) + n \\ &= [T(n-2) + (n-1)] + n \\ &= [T(n-3) + (n-2)] + (n-1) + n \\ &\dots \\ &= T(0) + 1 + 2 + \dots + n \end{aligned}$$

这里有个关键点：每次展开，我们都在累加一个数，而且这个数是从 1 到 n 的等差数列。所以 $T(n)$ 实际上等于 $T(0)$ 加上从 1 加到 n 的和。