时间复杂度是CSP-J初赛的必考内容约2-4分也是复赛分析程序性能的基础。下面我从定义→推导→题型→例题完整梳理。一、时间复杂度的核心概念1.1 什么是时间复杂度定义算法中基本操作的执行次数随问题规模 n 的增长趋势。大O表示法只保留最高阶项忽略常数系数和低阶项。记号含义举例O(1)常数时间数组随机访问O(log n)对数时间二分查找O(n)线性时间单层循环O(n log n)线性对数时间归并排序O(n²)平方时间冒泡排序O(n³)立方时间三重循环O(2ⁿ)指数时间斐波那契递归O(n!)阶乘时间全排列口诀1log⁡nnnlog⁡nn2n32nn!1lognnnlognn2n32nn!二、时间复杂度计算的三步法找基本操作循环体或递归调用计算执行次数数学表达式取最高阶去系数三、所有题型分类题型1单层循环题目以下代码的时间复杂度是 cppfor (int i 0; i n; i) { cout i endl; }答案O(n)解析循环执行 n 次每次 O(1)总 O(n)。题目以下代码的时间复杂度是 cppfor (int i 0; i n; i 2) { cout i endl; }答案O(n)解析循环执行 n/2 次系数 1/2 忽略仍为 O(n)。题目以下代码的时间复杂度是 cppfor (int i 1; i n; i * 2) { cout i endl; }答案O(log n)解析i 的变化1, 2, 4, 8, ... 直到 n执行次数 k 满足 2^k n → k ⌊log₂n⌋时间复杂度 O(log n)。题型2双层循环相乘题目以下代码的时间复杂度是 cppfor (int i 0; i n; i) { for (int j 0; j n; j) { cout i j endl; } }答案O(n²)解析外层 n 次每次内层 n 次总 n×n n²。题目以下代码的时间复杂度是 cppfor (int i 0; i n; i) { for (int j 0; j i; j) { cout i j endl; } }答案O(n²)解析执行次数 0 1 2 ... (n-1) n(n-1)/2最高阶为 n²/2忽略系数 → O(n²)。题型3三重循环答案O(n³)题型4条件终止循环题目以下代码的时间复杂度是 cppfor (int i 0; i n; i) { for (int j 0; j n; j) { if (i j) break; cout i j endl; } }答案O(n²)解析内层循环当 j i 时 break。总执行次数 12...n n(n1)/2 → O(n²)。题型5递归算法题目以下代码的时间复杂度是 cppint fib(int n) { if (n 1) return n; return fib(n-1) fib(n-2); }答案O(2ⁿ)解析递推式 T(n) T(n-1) T(n-2) O(1)解出 T(n) ≈ 2ⁿ。记忆斐波那契递归 指数时间。题目以下代码的时间复杂度是 cppint fact(int n) { if (n 1) return 1; return n * fact(n-1); }答案O(n)解析T(n) T(n-1) O(1)递归深度 n → O(n)。题型6主定理Master Theorem题型主定理公式对于 T(n) aT(n/b) f(n)情况条件复杂度情况1f(n) O(n^{log_b a - ε})T(n) Θ(n^{log_b a})情况2f(n) Θ(n^{log_b a})T(n) Θ(n^{log_b a} log n)情况3f(n) Ω(n^{log_b a ε}) 且 af(n/b) ≤ cf(n)T(n) Θ(f(n))CSP-J简化版只需会计算T(n) 2T(n/2) O(n)这种类型。题目归并排序的时间复杂度满足 T(n) 2T(n/2) O(n)结果是 答案O(n log n)解析a2, b2, n^{log₂2}nf(n)n情况2T(n) Θ(n log n)。题目T(n) 2T(n/2) O(1) 的时间复杂度是 答案O(n)解析a2, b2, n^{log₂2}nf(n)1 O(n^{1-1})情况1T(n) O(n)。题型7多重循环中隐藏的 log题目以下代码的时间复杂度是 cppfor (int i 1; i n; i) { for (int j 1; j n; j * 2) { cout i j endl; } }答案O(n log n)解析外层 O(n)内层 O(log n)总 O(n log n)。题型8函数调用嵌套题目以下代码的时间复杂度是 cppvoid func(int n) { for (int i 0; i n; i) { cout i endl; } } void solve(int n) { for (int i 0; i n; i) { func(i); } }答案O(n²)解析func(i) 执行 i 次总执行次数 0 1 2 ... (n-1) n(n-1)/2 → O(n²)。题型9二分查找与递归题目二分查找的时间复杂度是 答案O(log n)解析每次将搜索范围缩小一半n → n/2 → n/4 → ... → 1需 log₂n 次每次 O(1)总 O(log n)。题型10while 循环题目以下代码的时间复杂度是 cppint i 1; while (i n) { cout i endl; i * 3; }答案O(log₃ n) O(log n)解析i 的变化1, 3, 9, 27, ...执行 log₃ n 次。底数无关统一记为 O(log n)。题目以下代码的时间复杂度是 cppint i n; while (i 1) { cout i endl; i / 2; }答案O(log n)解析i: n → n/2 → n/4 → ... → 1执行 log₂ n 次。题型11嵌套循环中内层依赖外层平方题目以下代码的时间复杂度是 cppfor (int i 0; i n; i) { for (int j 0; j i * i; j) { cout i j endl; } }答案O(n³)解析总执行次数 0² 1² 2² ... (n-1)² n(n-1)(2n-1)/6最高阶为 n³/3 → O(n³)。题型12复杂度比较排序题目以下时间复杂度按从小到大排列正确的是 A. O(1) O(log n) O(n) O(n log n) O(n²) O(2ⁿ)B. O(1) O(n) O(log n) O(n log n) O(n²) O(2ⁿ)C. O(1) O(log n) O(n log n) O(n) O(n²) O(2ⁿ)D. O(log n) O(1) O(n) O(n log n) O(n²) O(2ⁿ)答案A解析正确顺序O(1) O(log n) O(n) O(n log n) O(n²) O(n³) O(2ⁿ) O(n!)选A。题型13多个程序段相加题目以下代码的时间复杂度是 cppfor (int i 0; i n; i) { cout i endl; } for (int i 0; i n; i) { for (int j 0; j n; j) { cout i j endl; } }答案O(n²)解析第一段 O(n)第二段 O(n²)取最高阶 → O(n²)。题型14图论算法的时间复杂度题目以下图论算法的时间复杂度匹配正确的是 A. DFS/BFS邻接矩阵O(V²) B. DFS/BFS邻接表O(E²)C. Dijkstra普通O(V²) D. Floyd三维循环O(V³)答案A、C、D都正确B错误解析DFS/BFS 邻接矩阵O(V²)DFS/BFS 邻接表O(VE)Dijkstra 普通实现O(V²)FloydO(V³)选A、C、D。题型15手算最坏情况阅读程序题题目阅读以下程序最坏情况下时间复杂度是 cppint find(int a[], int n, int x) { for (int i 0; i n; i) { if (a[i] x) return i; } return -1; }答案O(n)解析最坏情况x 在数组末尾或不存在循环 n 次 → O(n)。题型16与空间复杂度对比题目归并排序的时间复杂度和空间复杂度分别是 A. O(n log n)O(n) B. O(n²)O(n)C. O(n log n)O(log n) D. O(n²)O(1)答案A解析归并排序时间 O(n log n)空间 O(n)。选A。四、时间复杂度速查表一排序算法算法最好平均最坏空间冒泡排序O(n)O(n²)O(n²)O(1)选择排序O(n²)O(n²)O(n²)O(1)插入排序O(n)O(n²)O(n²)O(1)快速排序O(n log n)O(n log n)O(n²)O(log n)归并排序O(n log n)O(n log n)O(n log n)O(n)堆排序O(n log n)O(n log n)O(n log n)O(1)希尔排序O(n log n)O(n^1.3)O(n²)O(1)计数排序O(nk)O(nk)O(nk)O(k)基数排序O(d(nk))O(d(nk))O(d(nk))O(nk)桶排序O(nk)O(nk)O(n²)O(nk)二查找算法算法时间复杂度顺序查找O(n)二分查找O(log n)三图论算法算法时间复杂度DFS/BFS邻接矩阵O(V²)DFS/BFS邻接表O(VE)Dijkstra普通O(V²)Dijkstra堆优化O((VE)log V)FloydO(V³)Prim普通O(V²)KruskalO(E log E)五、时间复杂度推导方法总结一循环类循环模式复杂度单层循环 i: 0→nO(n)单层循环 i: 0→n, icO(n)单层循环 i: 1→n, i*2O(log n)双层完全嵌套O(n²)双层内层依赖外层O(n²)双层外层 n内层 logO(n log n)三重完全嵌套O(n³)二递归类递推式复杂度T(n)T(n-1)O(1)O(n)T(n)T(n-1)O(n)O(n²)T(n)2T(n-1)O(1)O(2ⁿ)T(n)2T(n/2)O(1)O(n)T(n)2T(n/2)O(n)O(n log n)T(n)T(n/2)O(1)O(log n)六、实战检测题号题目1for (int i 0; i n; i)for (int j i; j n; j * 2)2while (i n) {i * 2;}3快速排序最坏情况4for (int i 0; i n; i) {for (int j 0; j 100; j) { ... }}5T(n) 2T(n/2) O(n²)主定理6斐波那契递归时间复杂度7二分查找时间复杂度8选择排序平均时间复杂度9for (int i 0; i n; i) {for (int j 0; j n; j 2) { ... }}10for (int i 0; i n; i) {for (int j 0; j i; j) {for (int k 0; k j; k) { ... }}}11哈希表查找平均时间复杂度12T(n) T(n/2) T(n/3) O(1)O(n log n)外层 n内层 log nO(log n)O(n²)O(n)内层常数次O(n²)主定理情况3O(2ⁿ)O(log n)O(n²)O(n²)内层 n/2 次系数忽略O(n³)C(n,3) n³/6O(1)平均O(n)最坏O(n)递归树展开每层 T(n) 约减小到 5n/6深度 O(log n)但分支数...实际为 O(n)最后建议时间复杂度题的关键是学会数循环的执行次数而不是死记公式。掌握三种模式就够了循环次数 等差数列求和 → 最高阶加1循环步长指数增长 → log n递归用递推式展开 → 看递归树深度把这16种题型练透考试时遇到任何时间复杂度题都能应对。七、空间复杂度八、流程图九、伪代码