GESP 四级 · GESP 202412 C++ 四级 第 21 题

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

答案A。综合分析各选项，运用相关知识推导。

仔细审题，注意"不正确""不属于""不是"等否定词。用排除法缩小范围。

【考点】递推关系求解｜时间复杂度分析｜数学归纳

1. 🎯 考纲定位

本题考查 GESP 四级大纲中"递推关系与时间复杂度"的核心考点。命题人利用考生对递推式与复杂度混淆的弱点，将"累加 n"这一线性操作嵌套在递归结构中，制造出看似 O(n) 实则 O(n²) 的陷阱。四级递推从未考过求和，此题本质是披着算法外衣的数学题——卡住的是那些只会套"二分 O(log n)""递归 O(n)"口诀的考生。