NOIP 提高 2018 第一轮 第 5 题：设某算法的时间复杂度函数的递推方程是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 ⇒ O(n²)。

选 D。

易错提醒

① 与普及组同题；② Σk 展开。