算法复杂度估算方法

复杂度估算是 GESP C++ 五级知识块 2 的独立考点：要求掌握算法复杂度估算方法，尤其含多项式（如 $O(n)$、$O(n^2)$）与对数（如 $O(\log n)$、$O(n\log n)$）的复杂度。本章补充分章，因为五级大纲把它与大整数、链表、二分、递归、分治、贪心并列为核心知识块，而前 8 章（41–48）未设专门章节。掌握复杂度，才能在选择算法时判断"会不会超时"。

注：本章为对五级大纲块 2 的集中补充，与第 45–48 章中分散的复杂度分析互为呼应。

1. 为什么要估算复杂度

程序运行受时间与内存限制（竞赛/考试常有 1–2 秒时限）。复杂度估算让我们在动手前就能判断：对给定的数据规模 $n$，某算法是否会超时或超内存。核心结论：$n$ 较大时，复杂度阶数决定成败，常数系数影响很小。

2. 大 O 记号（渐进上界）

用 $O(f(n))$ 表示算法在最坏情况下随 $n$ 增长的"量级上界"。只保留增长最快的项、忽略常数系数：

• $O(1)$：常数时间，与 $n$ 无关；
• $O(\log n)$：对数时间（如二分）；
• $O(n)$：线性时间（如单层循环）；
• $O(n \log n)$：线性对数（如归并、快排平均）；
• $O(n^2)$：平方时间（如双重循环）；
• $O(2^n)$：指数时间（如朴素斐波那契）。

GESP 五级重点：能识别并估算"多项式复杂度"（$O(n^k)$，如 $O(n)$、$O(n^2)$）与"对数复杂度"（$O(\log n)$、$O(n\log n)$）。

3. 时间复杂度怎么估

3.1 看循环层数

• 单重循环、for 内操作为 $O(1)$ → $O(n)$；
• 双重嵌套循环、内外都与 $n$ 相关 → $O(n^2)$；
• 循环变量按倍数变化（如 i *= 2）→ $O(\log n)$。

// 例1：O(n)
for (int i = 0; i < n; i++) sum += a[i];

// 例2：O(n^2)
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) c[i][j] = a[i] + b[j];

// 例3：O(log n)
for (int i = 1; i < n; i *= 2) cnt++; // 或二分查找

3.2 看递归（主定理速判）

对分治递归 $T(n) = a\,T(n/b) + O(n^c)$：

• $\log_b a > c$ → $O(n^{\log_b a})$
• $\log_b a = c$ → $O(n^c \log n)$
• $\log_b a < c$ → $O(n^c)$

例：归并排序 $a=2,b=2,c=1$ → $\log_2 2 = 1 = c$ → $O(n\log n)$。

3.3 空间复杂度

看"额外开了多大的辅助存储"：

• 几个变量 → $O(1)$；
• 一维数组/递归栈深 $n$ → $O(n)$；
• 二维数组 $n \times n$ → $O(n^2)$；
• 递归栈深度 = 递归最大深度（如阶乘 $O(n)$、二分 $O(\log n)$）。

4. 典型复杂度速查表

5. 估算练习

1. 下列代码中基本操作执行次数约为多少（设 $n$ 很大）？

int cnt = 0;
for (int i = 1; i <= n; i *= 2)
    for (int j = 0; j < n; j++)
        cnt++;

外层 i *= 2 约 $\log_2 n$ 次，内层 $n$ 次 → 总 $O(n \log n)$。

2. 若某题 $n \le 10^5$、时限 1 秒，应优先选择哪种量级算法？ 答：一般 $O(n\log n)$ 或 $O(n)$ 安全；$O(n^2)$ 约 $10^{10}$ 次会超时；$O(2^n)$ 更不行。

6. 选择题练习

1. 下列复杂度中，增长速度最慢的是： A. $O(n^2)$ B. $O(n \log n)$ C. $O(\log n)$ D. $O(n)$

   查看答案

   答案：C。对数复杂度随 $n$ 增长最慢，其次依次为 $O(n)$、$O(n\log n)$、$O(n^2)$。

2. 以下代码的时间复杂度是：

   for (int i = 0; i < n; i++)
       for (int j = i; j < n; j++)
           sum++;
   

   A. $O(n)$ B. $O(n \log n)$ C. $O(n^2)$ D. $O(\log n)$

   查看答案

   答案：C。内层循环次数约为 $n + (n-1) + \dots + 1 = n(n+1)/2$，属 $O(n^2)$。

3. 二分查找的时间复杂度属于哪一类？ A. 多项式 $O(n)$ B. 对数 $O(\log n)$ C. 平方 $O(n^2)$ D. 指数 $O(2^n)$

   查看答案

   答案：B。每次折半，比较次数约 $\log_2 n$，属于对数复杂度，是五级重点。

4. 归并排序的平均时间复杂度是： A. $O(n)$ B. $O(n \log n)$ C. $O(n^2)$ D. $O(\log n)$

   查看答案

   答案：B。归并排序每层合并 $O(n)$、共 $\log n$ 层，稳定 $O(n\log n)$，属"多项式×对数"量级。

5. 一个递归函数 f(n) 每次调用产生 2 个规模为 $n/2$ 的子问题，合并开销 $O(n)$，其复杂度约为： A. $O(n)$ B. $O(n \log n)$ C. $O(n^2)$ D. $O(2^n)$

   查看答案

   答案：B。由主定理，$a=2,b=2,c=1$，$\log_2 2 = c = 1$，复杂度为 $O(n\log n)$。