本练习共12题涵盖CSP-J初赛/复赛中时间复杂度计算的所有核心题型按难度递进编排。题型包括单层循环、双层循环普通嵌套与关联嵌套、递推关系式、递归函数、经典算法复杂度、综合阅读程序等。 第一梯队基础入门第1-4题目标掌握单层循环和简单嵌套循环的复杂度计算能识别O(1)、O(log n)、O(n)、O(n²)等基本复杂度。第1题★☆☆☆☆下列代码片段的时间复杂度是cppfor (int i 1; i n; i) { cout i endl; }A. O(1) B. O(log n) C. O(n) D. O(n²)答案C解析循环从1到n执行n次时间复杂度O(n)。第2题★☆☆☆☆下列代码片段的时间复杂度是cppfor (int i 1; i n; i * 2) { cout i endl; }A. O(1) B. O(log n) C. O(n) D. O(n log n)答案B解析i的取值为1, 2, 4, 8, ..., 2^k循环次数为⌊log₂n⌋1时间复杂度O(log n)。第3题★★☆☆☆下列代码片段的时间复杂度是cppfor (int i 1; i n; i) { for (int j 1; j n; j) { sum; } }A. O(n) B. O(n log n) C. O(n²) D. O(log n)答案C解析外层循环n次内层循环每次n次总执行n×n n²次时间复杂度O(n²)。第4题★★☆☆☆下列代码片段的时间复杂度是cppfor (int i 1; i n; i) { for (int j 1; j i; j * 2) { cout i j endl; } }A. O(n) B. O(n log n) C. O(n²) D. O(log n)答案B解析外层循环n次。内层循环条件j ij每次乘以2执行次数为⌊log₂i⌋1。总执行次数 Σᵢ₌₁ⁿ (⌊log₂i⌋1) O(n log n)。注意内层上限是i而非n但求和后依然为O(n log n)。⚡ 第二梯队递推与递归第5-7题目标掌握通过递推式计算递归算法的时间复杂度包括线性递归、分治递归等。第5题★★☆☆☆某算法的时间复杂度满足递推关系式T(n) T(n-1) O(1)且T(1) 1则该算法的时间复杂度为A. O(1) B. O(log n) C. O(n) D. O(n²)答案C解析展开递推T(n) T(n-1) 1 T(n-2) 2 ... T(1) (n-1) n故T(n) O(n)。对应于线性递归如单向链表遍历。第6题★★★☆☆某算法的时间复杂度满足递推关系式T(n) 2T(n/2) O(n)且T(1) 1则该算法的时间复杂度为A. O(log n) B. O(n) C. O(n log n) D. O(n²)答案C解析这是典型的分治递归每次将问题分为2个子问题每个子问题规模为n/2合并代价为O(n)。根据主定理Master TheoremT(n) aT(n/b) f(n)其中a2, b2, f(n)O(n)。因为log_ba log₂2 1f(n) O(n) O(n^1)属于情况2所以T(n) O(n log n)。对应于归并排序的时间复杂度。第7题★★★☆☆某算法的时间复杂度满足递推关系式T(n) T(n/2) O(1)则该算法的时间复杂度为A. O(1) B. O(log n) C. O(n) D. O(n log n)答案B解析T(n) T(n/2) 1展开得T(n) T(n/4) 1 1 ... T(1) log₂n O(log n)。对应于二分查找的时间复杂度。 第三梯队经典算法复杂度第8-10题目标掌握排序、筛法等经典算法的时间复杂度这是初赛选择题的常考内容。第8题★★☆☆☆使用埃拉托斯特尼筛法埃氏筛求 1 到 N 之间的所有素数其时间复杂度接近A. O(N) B. O(N log log N) C. O(N log N) D. O(N²)答案B解析埃氏筛总操作次数 N × Σ_{p≤N} 1/p ≈ N × log log N故时间复杂度为O(N log log N)。这是梅滕斯定理的直接应用。第9题★★☆☆☆归并排序无论初始状态如何时间复杂度始终稳定在A. O(n) B. O(n log n) C. O(n²) D. O(log n)答案B解析归并排序采用分治策略T(n)2T(n/2)O(n)由主定理得O(n log n)。最好、最坏、平均情况均为O(n log n)。第10题★★★☆☆快速排序在最坏情况下的时间复杂度为 O(n²)。为避免最坏情况常采用的优化策略是A. 随机选择基准 B. 使用插入排序替代 C. 增加递归深度 D. 使用堆排序答案A解析快速排序最坏情况发生在每次选择的基准都是当前子数组的最大或最小值导致划分严重不平衡。随机选择基准可以使得最坏情况发生的概率极低从而将期望时间复杂度稳定在O(n log n)。B、C、D都不是针对快速排序优化基准选择的策略。 第四梯队综合阅读与实战第11-12题目标模拟初赛阅读程序题需要结合代码逻辑分析整体复杂度。第11题★★★★☆阅读以下程序其时间复杂度为cppint d[10] {0}, ans 0; for (int i 0; i n; i) { int p 0; d[p]; while (d[p] k) { d[p] 0; p; d[p]; ans; } }该程序模拟 k 进制下的进位过程每次循环最多进位 logₖ n 次但总进位次数约为 n 次A. O(n) B. O(n log n) C. O(n²) D. O(log n)答案A解析这是一个摊还分析Amortized Analysis的典型例子。外层循环执行n次内层while单次可能执行O(logₖ n)次最高位进位但所有迭代中while的总执行次数不超过O(n)。为什么因为每次while执行都代表一次进位操作k进制计数器从0递增到n总进位次数约等于 n/(k-1)即O(n)。所以总时间复杂度为O(n)而非表面上看到的O(n log n)。理解难点不能简单用“外层n次 × 内层最多log n次”计算需要分析总操作次数。第12题★★★★★若某算法在n 1000时耗时 10ms该算法的时间复杂度为O(N log N)。当n增加到 10000 时预计运行时间约为A. 100ms B. 133ms C. 150ms D. 200ms答案B解析O(N log N) 表示时间与n log n成正比。计算比例n₁ 1000n₁ log₂ n₁ 1000 × 10 10000n₂ 10000n₂ log₂ n₂ 10000 × 14 140000比例 140000 / 10000 14预计耗时 10ms × 14 140ms → 选B133ms因为选项中最接近的是B。若以自然对数计算n₂ ln n₂ / (n₁ ln n₁) ≈ 10000×9.21 / (1000×6.91) ≈ 13.3 → 133ms 题型分布速查表题号难度题型答案核心考点1★☆☆☆☆单层循环CO(n)2★☆☆☆☆单层循环步长翻倍BO(log n)3★★☆☆☆普通双层循环CO(n²)4★★☆☆☆关联双层循环BO(n log n)5★★☆☆☆递推式CT(n)T(n-1)O(1) → O(n)6★★★☆☆递推式主定理CT(n)2T(n/2)O(n) → O(n log n)7★★★☆☆递推式BT(n)T(n/2)O(1) → O(log n)8★★☆☆☆经典算法B埃氏筛 O(N log log N)9★★☆☆☆经典算法B归并排序 O(n log n)10★★★☆☆算法优化A随机基准避免快排最坏情况11★★★★☆摊还分析Awhile总执行次数O(n)12★★★★★复杂度估计B根据复杂度推导运行时间 补充说明第4题易错点内层循环上限是变量i而非常量n很多初学者会误判为O(n²)但实际上Σ log i log(n!) O(n log n)。第11题难度最高摊还分析是初赛阅读程序题的难点需理解“总进位次数”而非单次复杂度。类似题型可参考CSP-J 2020年阅读程序题。第12题需注意底数选择时间复杂度中log底数对复杂度的“阶”无影响但在估算实际运行时间时若涉及具体数值计算需统一底数。本题用log₂得到140ms用ln得到133ms选项中133更接近建议默认使用自然对数或常用对数关键是比较倍数关系。