(9) 简单算法复杂度的估算

GESP C++四级官方考试大纲中，共有11条考点，本文针对第9条考点进行分析介绍。

（9）简单算法复杂度的估算，含多项式、指数复杂度。

四级其他考点回顾：

• 【GESP】C++四级考试大纲知识点梳理, (1) 指针
• 【GESP】C++四级考试大纲知识点梳理, (2) 结构体和二维数组
• 【GESP】C++四级考试大纲知识点梳理, (3) 模块化和函数
• 【GESP】C++四级考试大纲知识点梳理, (4) 变量和作用域
• 【GESP】C++四级考试大纲知识点梳理, (5) 值传递
• 【GESP】C++四级考试大纲知识点梳理, (6) 递推算法
• 【GESP】C++四级考试大纲知识点梳理, (7) 排序算法基本概念
• 【GESP】C++四级考试大纲知识点梳理, (8) 冒泡、插入、选择排序

一、什么是算法复杂度？

算法复杂度用于衡量算法运行时间或占用空间随输入规模变化的增长速度。

• 时间复杂度：关注算法执行时间。
• 空间复杂度：关注算法占用的内存。

本文重点介绍时间复杂及其估计。

二、常见算法时间复杂度

时间复杂度（Time Complexity）是用来描述算法在输入规模 n 增大时，执行所需基本操作次数的增长速度。

我们用大 $O$ 记号来表示，例如：

• $O(1)$：与输入无关（常数时间）
• $O(n)$：线性增长
• $O(n^2)$：平方增长
• $O(2^n)$：指数增长
• $O(n!)$：阶乘增长

2.1 常见时间复杂度总结对比表

2.1.1 【特别说明】多项式复杂度

多项式复杂度（Polynomial Time Complexity）是指算法的时间复杂度可以用多项式表示，即：

• 形如 $O(n^k)$，其中 k 为常数
• 常见的有 $O(1)$、$O(n)$、$O(n^2)$、$O(n^3)$ 等
• 特点：随输入规模 n 增长相对平缓
• 一般认为是"可解"的复杂度级别

2.1.2 【特别说明】指数复杂度

指数复杂度（Exponential Time Complexity）是指算法的时间复杂度呈指数增长，即：

• 形如 $O(k^n)$，其中 k 为常数，n 为输入规模
• 常见的有 $O(2^n)$、$O(3^n)$ 等
• 特点：随输入规模 n 增长极快
• 一般认为是"难解"的复杂度级别
• 典型问题如：子集枚举、递归斐波那契等

2.2 不同复杂度时间增长速度示意

✅ 多项式复杂度随着 n 增长是平稳的

❌ 指数/阶乘复杂度很快无法承受，程序跑不动

2.3 根据输入规模选择算法

在实际编程中，需要根据输入规模选择合适的算法。以下是一个简单的参考指南：

2.3.1 算法选择注意事项

1. 考虑实际约束

   • 时间限制（通常1-2秒）
   • 内存限制（通常64-256MB）
   • CPU速度（一般1秒可执行10⁸左右基本运算）

2. 权衡取舍

   • 代码实现难度
   • 算法可读性和可维护性
   • 实际运行效率（常数因子）

3. 特殊情况考虑

   • 输入数据特征（如已排序、近似排序）
   • 空间复杂度要求
   • 算法稳定性需求

2.3.2 实践建议

• 小规模数据：优先选择容易实现的算法
• 大规模数据：必须考虑算法效率
• 关键场景：可以牺牲代码简洁性换取性能
• 通用场景：在可接受范围内优先选择可维护性好的方案

三、算法复杂度判断一般步骤

判断一个算法的时间复杂度，核心在于分析：随着输入规模 n 增大，算法的基本操作（如加法、比较、赋值）执行次数增长速度如何。

📌 第一步：找出基本操作：

• 通常是最内层循环中重复执行的操作，如加法、比较、递归调用等。

📌 第二步：分析控制结构（顺序/分支/循环/递归）：

• 顺序结构：多个操作的复杂度相加，如 $O(n) + O(n^2)$，根据加法规则只保留最大项 $O(n^2)$
• 条件结构：if-else 分支取时间复杂度较大的那个分支，如 if 分支是 $O(n)$，else 分支是 $O(n^2)$，则取 $O(n^2)$
• 循环结构：分析循环变量的变化规律，如 for(i=0;i<n;i++) 执行 n 次，复杂度为 $O(n)$
• 递归结构：先写出递归方程，如 $T(n) = T(n-1) + 1$，然后求解得到复杂度 $O(n)$

📌 第三步：用渐进符号 $O$ 表示:

• 只保留最高阶项，忽略常数因子和低阶项。例如:
  • $3n^2 + 2n + 1 \rightarrow O(n^2)$
  • $n^3 + 100n^2 \rightarrow O(n^3)$
  • $2^n + n^2 \rightarrow O(2^n)$

3.1 举例说明

例1：简单循环

for (int i = 0; i < n; i++) {
    cout << i << endl;
}

• 基本操作：cout 执行 n 次
• 复杂度：$O(n)$（线性复杂度）

例2：嵌套循环

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cout << i << "," << j << endl;
    }
}

• 外层执行 $n$ 次，内层每次执行 $n$ 次
• 总操作次数：$n × n = n^2$
• 复杂度：$O(n^2)$（二次复杂度）

例3：不等长嵌套循环

for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        cout << i << "," << j << endl;
    }
}

• $j$ 从 $0$ 到 $i-1 \rightarrow$ 总执行次数为 $1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2}$
• 复杂度：$O(n^2)$（仍然是平方）

例4：对数型复杂度$(log n)$

int i = 1;
while (i < n) {
    i = i * 2;
}

• $i$ 每次乘 2：1 → 2 → 4 → 8 → … → n
• 执行次数 $\approx \log_2(n)$
• 复杂度：$O(log n)$（对数复杂度）

例5：递归斐波那契（指数复杂度）

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

• 每次调用都拆成两个子问题
• 形成一棵递归树，总节点约 $2^n$
• 复杂度：$O(2^n)$（指数复杂度）

例6：全排列问题（阶乘复杂度）

void permute(string s, int l, int r) {
    if (l == r) {
        cout << s << endl;
    } else {
        for (int i = l; i <= r; i++) {
            swap(s[l], s[i]);
            permute(s, l + 1, r);
            swap(s[l], s[i]);
        }
    }
}

• 每个字符都和第一个字符交换，共 $n$ 次
• 每个字符都和第二个字符交换，共 $n-1$ 次
• 每个字符都和第三个字符交换，共 $n-2$ 次
• 总次数：$n + (n-1) + (n-2) + \cdots + 1 = n(n+1)/2$
• 复杂度：$O(n!)$

3.2 常见结构对应复杂度口诀

四、总结要点

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号