NOIP 提高组初赛 · NOIP 2015 提高组初赛试题 第 10 题

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

拿到递推式别慌，核心就两步：先把 T(n) 像剥洋葱一样一层层展开，直到露出底层的 T(0)；然后你会看到一堆数字在求和，算出这个和的阶数，答案自然出来了。

很多同学看到 T(n) = T(n-1) + n，脑子里蹦出“递归树”或者“每次加一个 n”，容易误判成 O(n log n) 甚至 O(n)。其实这里没有分治，每次只减少 1，相当于把 1 到 n 的所有整数都加了一遍，累加的结果是 n² 量级，而不是对数级或线性级，这是命题人最爱挖的坑。

考点概念：递推式求时间复杂度

这道题考的是递推展开 + 求和阶数判断。给你一个递推关系式 T(n) = T(n-1) + n，以及边界条件 T(0) = 1，让你求时间复杂度。

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

命题人特别喜欢用这种“看起来像 O(n) 或 O(n log n)”的递推式来迷惑人。它没有分治的“一半一半”结构，也没有对数级的递归层数，而是线性递减（n, n-1, n-2...）。如果你只盯着“每次加一个 n”，很容易脑补成 O(n log n)；如果你只盯着“递归了 n 层”，可能会误判成 O(n)。这道题就是专门测试你是否能透过现象看本质——展开后到底在算什么。在历年 NOIP 和 CSP 中，这类递推展开题出现频率不低，是基础算法分析的高频考点。