11 复杂度与文件操作

正在加载视频播放器…

GESP C++ 四级讲：复杂度与文件操作系统梳理

核心目标：理解算法复杂度（时间与空间）的基本概念，掌握多项式与指数复杂度的估算方法，能根据代码快速判断复杂度；掌握文件重定向（freopen）与文件流（ifstream/ofstream）的读写操作，能判断不同文件操作方式的正确性。
复杂度看“循环层数”和“递归树结构”，多项式可控、指数爆炸；文件操作分清“重定向”与“文件流”两条路，freopen换标准流，ifstream/ofstream管文件流。

第一部分：算法复杂度

1. 复杂度考纲定位

根据CCF官方考纲，四级知识内容明确包含 “简单算法复杂度的估算（含多项式、指数复杂度）” 。四级要求掌握的是简单算法的复杂度估算，重点是多层循环和基础递归的复杂度分析，不涉及高级数据结构（如线段树、平衡树）的复杂度推导。

四级复杂度考点的常见考法：

考法	说明	典型题目
循环嵌套复杂度判断	根据循环层数和终止条件判断复杂度	双重循环 O(n²)、指数循环 O(2ⁿ)
递归复杂度判断	根据递归树结构判断复杂度	斐波那契递归 O(2ⁿ)
排序算法复杂度	冒泡、选择、插入排序的复杂度	O(n²)
复杂度比较	比较不同复杂度的增长快慢	O(1) < O(log n) < O(n) < O(n²) < O(2ⁿ) < O(n!)

2. 什么是算法复杂度

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

时间复杂度：关注算法执行时间，即基本操作次数的增长速度。
空间复杂度：关注算法占用的内存，即额外存储空间的增长速度。

四级重点考查时间复杂度。

3. 常见时间复杂度一览

复杂度	名称	典型场景	四级考频
O(1)	常数级	数组元素访问、简单赋值	低
O(log n)	对数级	二分查找	低（五级重点）
O(n)	线性级	单层循环遍历数组	高
O(n log n)	线性对数级	快速排序、归并排序	低（五级重点）
O(n²)	平方级	双重嵌套循环、冒泡/选择/插入排序	最高频
O(n³)	立方级	三重嵌套循环、矩阵乘法	中
O(2ⁿ)	指数级	子集枚举、递归斐波那契	高频
O(n!)	阶乘级	全排列	低

4. 循环嵌套复杂度的判断方法

核心规律：时间复杂度 = 各层循环执行次数的乘积。

单层循环：

for (int i = 0; i < n; i++) {
    // 简单操作
}

执行 n 次，复杂度 O(n)。

双重嵌套循环：

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // 简单操作
    }
}

外层 n 次，内层 n 次，总计 n × n = n²，复杂度 O(n²)。

三重嵌套循环：

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
            // 简单操作
        }
    }
}

复杂度 O(n³)。

内层循环次数依赖外层变量：

for (int i = 0; i < n; i++) {
    for (int j = 0; j <= i; j++) {
        // 简单操作
    }
}

内层总次数 = 1 + 2 + 3 + … + n = n(n+1)/2，仍为 O(n²)。

记忆口诀：每多一层完整循环，复杂度多乘一个 n。

5. 指数复杂度的识别（四级高频）

指数复杂度 O(2ⁿ) 通常出现在以下场景：

场景一：循环次数是 2 的幂

for (int i = 0; i < (1 << n); i++) {   // 执行 2ⁿ 次
    // 简单操作
}

1 << n 等于 2ⁿ，外层循环执行 2ⁿ 次，复杂度 O(2ⁿ)。

场景二：外层 2ⁿ 次 + 内层 n 次

bool f(int arr[], int n, int target) {
    for (int i = 0; i < (1 << n); i++) {    // 2ⁿ 次
        int sum = 0;
        for (int j = 0; j < n; j++) {       // n 次
            if (i & (1 << j)) sum += arr[j];
        }
        if (sum == target) return true;
    }
    return false;
}

外层 2ⁿ 次，内层 n 次，总计 2ⁿ × n，复杂度 O(n × 2ⁿ)。

场景三：递归斐波那契

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

每次调用产生 2 个新调用，递归树节点数呈指数级增长，复杂度 O(2ⁿ)。

6. 复杂度估算真题

真题1（2023年9月） ：

对包含 n 个元素的数组进行冒泡排序，平均时间复杂度一般为（）。
A. O(n) B. O(n log n) C. O(n²) D. 以上都不正确
答案：C

真题2（2025年6月） ：

bool f(int arr[], int n, int target) {
 for (int i = 0; i < n; i++) {
     int sum = 0;
     for (int j = 0; j < n; j++) {
         if (i & (1 << j)) sum += arr[j];
     }
     if (sum == target) return true;
 }
 return false;
}
时间复杂度为（）。
答案：O(n²)。
解析：外层循环执行 n 次，内层循环也执行 n 次，总计 n² 次。内层的 if 条件判断不影响渐进复杂度。

真题3（2025年3月） ：

bool f(int arr[], int n, int target) {
 for (int i = 0; i < (1 << n); i++) {
     int sum = 0;
     for (int j = 0; j < n; j++) {
         if (i & (1 << j)) sum += arr[j];
     }
     if (sum == target) return true;
 }
 return false;
}
时间复杂度为（）。
答案：O(n × 2ⁿ)。
解析：关键区别在于外层循环次数是 2ⁿ（因为 1 << n 等于 2ⁿ），内层循环执行 n 次。

7. 空间复杂度简介

四级对空间复杂度要求较低，只需了解基本概念：

空间复杂度	典型场景
O(1)	只使用固定数量的变量
O(n)	使用长度为 n 的数组
O(n²)	使用二维数组

8. 复杂度易错点

只看循环层数，不看循环终止条件：for (i = 0; i < (1 << n); i++) 是 2ⁿ 次，不是 n 次。
被循环体内的复杂操作迷惑：循环体内的 if 判断、位运算等不影响渐进复杂度，只看循环执行次数。
混淆 1 << n 与 n：1 << n 是 2 的 n 次方，不是 n。
递归复杂度分析错误：斐波那契递归是 O(2ⁿ)，不是 O(n²)。
忽略内层循环依赖外层变量：j <= i 的内层循环总次数是 n(n+1)/2，仍为 O(n²)。

第二部分：文件操作

9. 文件操作考纲定位

四级考纲明确要求：“文件重定向与文件读写操作” 。具体要求是“掌握文件操作中的重定向，实现文件读写操作，了解文本文件的分类，掌握写操作、读操作、读写操作”。

四级文件操作的核心内容：

知识点	重要程度	考查形式
文件重定向 `freopen`	★★★★★	选择题高频
文件流 `ifstream`/`ofstream`	★★★★☆	选择题、判断题
文件打开模式	★★★☆☆	选择题
文件读写操作	★★★☆☆	编程题了解

10. 文件重定向 `freopen`

freopen 是C标准库函数，用于将标准输入/输出流重定向到文件。

语法：

freopen("文件名", "模式", 流指针);

参数	说明
文件名	字符串，指定文件路径
模式	`"r"` 读取、`"w"` 写入、`"a"` 追加
流指针	`stdin`（标准输入）、`stdout`（标准输出）、`stderr`（标准错误）

将输出重定向到文件：

#include <cstdio>
#include <iostream>
using namespace std;

int main() {
    freopen("log.txt", "w", stdout);   // 将标准输出重定向到 log.txt
    cout << "Welcome to GESP!" << endl; // 输出写入文件
    fclose(stdout);                     // 关闭文件
    return 0;
}

将输入重定向自文件：

freopen("input.txt", "r", stdin);   // 从 input.txt 读取输入
cin >> n;                            // 从文件读取，不是键盘

重定向的本质：把标准输入输出“指向”的对象从默认设备（键盘、屏幕）切换为文件。

记忆口诀：freopen 换水管，把 cin/cout 接到文件上。

11. 文件流 `ifstream` / `ofstream`

C++ 提供了专门的文件流类来进行文件读写，需要包含头文件 <fstream>。

文件输出流 ofstream（写文件）：

#include <fstream>
using namespace std;

int main() {
    ofstream outFile("log.txt");      // 创建文件输出流
    outFile << "Welcome to GESP!" << endl;  // 写入文件
    outFile.close();                   // 关闭文件
    return 0;
}

文件输入流 ifstream（读文件）：

#include <fstream>
using namespace std;

int main() {
    ifstream inFile("input.txt");     // 创建文件输入流
    int n;
    inFile >> n;                       // 从文件读取
    inFile.close();                    // 关闭文件
    return 0;
}

文件打开模式（ifstream/ofstream 构造函数的第二个参数）：

模式	含义	适用
`ios::in`	读取（默认 for ifstream）	ifstream
`ios::out`	写入（默认 for ofstream）	ofstream
`ios::app`	追加
`ios::trunc`	截断（覆盖）

12. 文件操作真题

真题（2024年12月） ：

下面哪种方式不能实现将字符串 "Welcome to GESP!" 输出重定向到文件 log.txt（）。
A. freopen("log.txt", "w", stdout); cout << "Welcome to GESP!" << endl; fclose(stdout);
B. std::ofstream outFile("log.txt"); outFile << "Welcome to GESP!" << endl; outFile.close();
C. std::ofstream outFile("log.txt"); cout << "Welcome to GESP!" << endl; outFile.close();
D. ofstream log_file("log.txt"); streambuf* org_cout = cout.rdbuf(); cout.rdbuf(log_file.rdbuf()); cout << "..."; cout.rdbuf(org_cout);
答案：C

解析：

A：使用 freopen 将标准输出重定向到文件，正确。
B：使用 ofstream 对象创建文件输出流，通过 outFile 输出，正确。
C 错误：创建了 ofstream 对象 outFile，但仍使用 cout 进行输出。cout 的输出不会自动写入 outFile，仍然输出到屏幕。
D：通过修改 cout 的缓冲区实现重定向，正确。

13. 文件操作易错点

混淆重定向与文件流：freopen 改变的是 cin/cout 的指向，ifstream/ofstream 是独立的文件流对象。
使用 ofstream 对象却用 cout 输出：cout 不会自动写入 ofstream 对象，这是真题中最常见的陷阱。
忘记包含头文件：freopen 需 <cstdio>，ifstream/ofstream 需 <fstream>。
忘记关闭文件：使用 close() 或 fclose() 确保数据写入磁盘。
文件打开模式混淆："w" 会覆盖原文件，"a" 是追加。
重定向后忘记恢复：在比赛中，重定向后通常不需要恢复，但了解 cout.rdbuf() 的恢复方式有助于理解原理。

第三部分：综合速查与真题清单

14. 核心速查表

模块	必记内容
O(n²)	双重嵌套循环、冒泡/选择/插入排序
O(2ⁿ)	`for (i = 0; i < (1 << n); i++)`、递归斐波那契
O(n × 2ⁿ)	外层 2ⁿ 次 + 内层 n 次
复杂度判断	看循环执行次数，不看循环体内部操作
`freopen` 重定向输出	`freopen("log.txt", "w", stdout);`
`freopen` 重定向输入	`freopen("input.txt", "r", stdin);`
`ofstream` 写文件	`ofstream out("log.txt"); out << ...;`
`ifstream` 读文件	`ifstream in("input.txt"); in >> n;`
文件流头文件	`<fstream>`
重定向头文件	`<cstdio>`
真题陷阱	创建 `ofstream` 对象却用 `cout` 输出，不能实现重定向

15. 总结

复杂度与文件操作是GESP四级从“正确”到“高效”和“完整”的关键模块。

复杂度看循环执行次数，不看循环体内部操作。
双重循环 O(n²)，三重循环 O(n³)。
1 << n 是 2 的 n 次方，不是 n。
递归斐波那契是 O(2ⁿ)，指数级增长极快。
freopen 用于重定向标准输入输出，换的是 cin/cout 的“水管”。
ifstream/ofstream 是独立的文件流对象，需要 <fstream>。
创建了 ofstream 对象却用 cout 输出，不能实现文件重定向——这是真题最高频陷阱。
多练“循环嵌套复杂度判断”“递归复杂度判断”“文件重定向方式判断”三类题。

复习建议：先把双重循环 O(n²) 和指数循环 O(2ⁿ) 的识别练熟，再掌握递归斐波那契的复杂度分析；文件操作重点区分 freopen 和 ofstream 两条路，牢记“创建了 ofstream 对象却用 cout 输出”是错误方式。考试中先判断题目考的是循环复杂度还是递归复杂度，再看文件操作是重定向还是文件流，最后对照选项逐一排除。