NOIP 提高组初赛 · NOIP 2018 提高组初赛试题 第 5 题

设某算法的时间复杂度函数的递推方程是 $T(n) = T(n - 1) + n$（$n$ 为正整数）及 $T(0) = 1$，则该算法的时间复杂度为（ ）。

这题本质就是反复累加。别急着套公式，顺着递推式一层层往下拆，把 T(n) 写成 T(n-1)+n，再把 T(n-1) 写成 T(n-2)+(n-1)，一直拆到 T(0)，你会发现它就是一个从 1 加到 n 的等差数列求和，量级直接就是 O(n²)。

最容易掉进两个坑：一是觉得递推里只有 +n，误以为整体是线性的，选了 O(n)；二是展开后看到 n 和 n-1 混在一起，没意识到这是等差数列，硬算成 O(n log n) 或者漏掉常数项导致量级判断错误。记住，T(n) 的每一项都是比前一项多一个 n-i，累加起来肯定是平方级的。

考点概念：递推式展开与等差数列求和

这道题考查的是如何通过递推关系式推导时间复杂度，核心就是把递推式展开，识别出其中的数学规律。题目给出的递推式是 $T(n) = T(n - 1) + n$，初始条件 $T(0) = 1$。很多同学看到递推式就慌，不知道从哪下手，其实只要顺着递推式一层一层往下拆，就能发现它就是一个简单的累加过程。

命题视角：为什么爱考这个？

命题人特别喜欢用这种“看似简单、实则需要展开”的递推式来挖坑。它表面看只是加一个 $n$，但 $T(n-1)$ 里又藏着一个 $n-1$，$T(n-2)$ 里又藏着一个 $n-2$……这种层层嵌套的累加，如果不展开，很容易误判为线性复杂度 $O(n)$。命题人就是想考你是否具备将递推式转化为数学求和公式的能力，以及是否能准确识别等差数列。