在仔细阅读了您分享的第 8 节和第 9 节大纲后，我为您整理了一份更为严谨、详细且符合实际比赛（如 CSP-J/S、NOIP）及工程开发标准的讲义。

针对您的原大纲，我做出了以下具有实战意义的学术补充与优化： 1. 本地调试与提交文件的智能切换（Conditional Compilation）：在 8.1 节中补充了利用宏定义 #ifndef ONLINE_JUDGE 自动切换文件输入输出的技巧，避免因为忘记注释 freopen 而导致在线测评（OJ）零分的“惨剧”。 2. 解除 C++ 流同步以提升速度（Fast I/O）：针对 8.2 节中“流速度较慢”的痛点，给出了在现代 C++ 中通过两行代码使流速度比肩甚至超越 scanf 的优化方案。 3. 数据类型与空间复杂度的精确换算：在 9.1 节中补充了将数组大小折算为具体内存（MB）的计算公式，帮助你在做题时准确判断程序是否会发生“内存超限”（MLE）。 4. 复杂度限度对照表（常识）：新增了在常见 1 秒时限内，不同数据范围 $N$ 对应的推荐算法复杂度上限。

以下是为您整理的讲义 Markdown 内容：

C++ 文件操作与算法复杂度讲义

8. 文件操作

在正式算法竞赛（如 CSP-S/NOIP、全国青少年信息学奥林匹克系列竞赛）中，通常要求程序从指定的 .in 文件读取输入，并将结果输出到指定的 .out 文件。如果未按要求使用文件操作，或者文件名写错一个字母，都将导致该题直接判为 0 分。

8.1 输入/输出重定向 (freopen)

这是竞赛中最通用、最推荐的文件操作方法。它能够将标准输入（键盘）和标准输出（屏幕）重定向到指定文件，而无需修改原有的 cin/cout 或 scanf/printf 代码。

A. 基本用法

#include <cstdio>  // freopen 所在的头文件
#include <iostream>

int main() {
    // 参数1：文件名； 参数2：读写模式 ("r"为读，"w"为写)； 参数3：重定向通道
    freopen("problem.in", "r", stdin);   // 重定向输入
    freopen("problem.out", "w", stdout); // 重定向输出

    int a, b;
    std::cin >> a >> b;                // 自动从 problem.in 读取
    std::cout << a + b << std::endl;   // 自动写入到 problem.out

    return 0;
}

B. 避坑指南与本地调试技巧

• 局限性：启用重定向后，命令行窗口将无法接受键盘输入。为了方便本地调试（键盘输入）与提交代码（文件输入）的快速切换，强烈推荐使用条件编译：

// 只有在非 OJ 环境下（即本地调试时）才执行文件重定向
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

大部分 Online Judge 会自动定义 ONLINE_JUDGE 宏，这样写可以保证本地调试时使用文件输入，提交到 OJ 时自动切回标准输入输出。

8.2 文件流 (fstream)

文件流是基于 C++ 面向对象机制的文件操作方式。

A. 基本用法

#include <fstream>

int main() {
    std::ifstream fin("problem.in");   // 定义输入文件流
    std::ofstream fout("problem.out"); // 定义输出文件流

    int a, b;
    if (fin >> a >> b) {               // 安全地读取数据
        fout << a + b << "\n";         // 写入文件
    }

    // 函数结束时，文件流析构函数会自动关闭文件
    return 0;
}

B. 速度优化（解除同步）

原笔记中提到“流的速度比较慢”。在默认情况下，由于 C++ 的 cin/cout 需要与 C 语言的 stdio（scanf/printf）保持同步，导致其输入输出速度确实较慢。

如果需要在大规模数据下使用流操作，可以通过在 main 函数开头添加以下两行代码，来解除同步并解绑输入输出，这样其速度将赶超 scanf/printf：

std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);

• 注意：解除同步后，严禁在同一个程序中混用 cin/cout 和 scanf/printf，否则会导致输出顺序错乱。

8.3 C 风格 FILE 指针与格式化函数

利用 FILE* 读写文件是 C 语言的标准做法，效率高且对格式控制精确。

A. 标准写法

#include <cstdio>

int main() {
    FILE *fin = fopen("problem.in", "r");
    FILE *fout = fopen("problem.out", "w");

    if (fin == nullptr || fout == nullptr) {
        return 1; // 打开文件失败时安全退出
    }

    int a, b;
    if (fscanf(fin, "%d%d", &a, &b) == 2) {
        fprintf(fout, "%d\n", a + b);
    }

    fclose(fin);  // 必须手动关闭文件，否则部分写入缓存可能丢失
    fclose(fout); 
    return 0;
}

9. 简单的算法分析和优化

9.1 时间复杂度与空间复杂度

在设计算法解决特定规模的数据时，必须先评估其时空开销。

A. 时间复杂度（Big O 记法）

时间复杂度表示随着输入规模 $n$ 的增大，算法执行的基本操作次数的增长趋势。我们只关注增长速度最快的主导项，并忽略其常数系数。 * 忽略常数：32 位的加法和 64 位的乘法在复杂度分析中都记为 $O(1)$ 常数操作。 * 多变量：如果输入由多个不相关的数据规模决定（如网格的长宽 $N$ 和 $M$），则时间复杂度应表示为 $O(NM)$。

B. 常见时间复杂度与数据范围对照表

通常，在算法竞赛中，程序的运行时间上限为 1.0 秒。以下是 1.0 秒内各种时间复杂度算法所能承受的最大数据规模 $N$：

C. 空间复杂度与内存换算

空间复杂度描述算法运行所需的辅助内存空间。在实际写程序时，需要严格控制全局数组或局部数组的大小，以防超出竞赛限定的内存（通常为 128MB, 256MB 或 512MB）。

内存换算核心公式：

$$\text{内存占用 (Bytes)} = \text{数组元素个数} \times \text{单个元素所占字节数}$$

各常见数据类型的单字节大小： * char / bool ：1 Byte * int / float ：4 Bytes * long long / double ：8 Bytes

$$\text{1 KB} = 1024 \text{ Bytes},\quad \text{1 MB} = 1024 \text{ KB} = 1,048,576 \text{ Bytes} \approx 10^6 \text{ Bytes}$$

实例演练：

如果在程序中声明了一个大小为 $10^7$ 的 int 数组： $$\text{Size} = 10^7 \times 4 \text{ Bytes} \approx 40,000,000 \text{ Bytes} \approx 38.15 \text{ MB}$$ 若题目空间限制为 128MB，该数组可以安全通过。

但如果声明了一个 $10000 \times 10000$ 的 int 二维数组： $$\text{Size} = 10000 \times 10000 \times 4 \text{ Bytes} = 4 \times 10^8 \text{ Bytes} \approx 381.47 \text{ MB}$$ 在 128MB 或 256MB 的限制下，程序在编译或运行阶段便会直接触发内存溢出错误。因此，大数组务必开在全局作用域内，且尽量避免冗余空间开销。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com