NOIP 提高 2015 第一轮 第 10 题：设某算法的计算时间表示为递推关系式 T(n) = T(n - 1) + n（n

题目

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

选项

• A. $O(\log n)$
• B. $O(n \log n)$
• C. $O(n)$
• D. $O(n^2)$

答案

D

题解

考点定位

本题考「递推复杂度」,对应大纲 4.1.1（难度【1】）。

解题过程

T(n)=T(n−1)+n ⇒ 1+n(n+1)/2 = O(n²)。

选 D。

易错提醒

① 与普及组同题；② 累加展开。