NOIP 普及 2015 第一轮 第 19 题：由递推式判断算法时间复杂度

题目

某算法的计算时间表示为递推关系式 $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（难度【2】）。

解题过程

T(n)=T(n−1)+n：

$$T(n)=T(0)+\sum_{k=1}^{n}k=1+\frac{n(n+1)}{2}=O(n^2)$$

选 D。

易错提醒

① 展开累加求和；② 对照 T(n)=T(n/2)+n 是 O(n)——减半与减一不同。