关于复杂度、文件操作、异常处理的详细讲解（从属于GESP四级）

本章内容

算法复杂度初步计算

C++ 异常处理机制入门

文件操作与重定向

一、算法复杂度初步计算

考纲在“简单算法复杂度的估算（含多项式、指数、对数复杂度）”一节明确要求考生能够 辨析 O(1) / O(log n) / O(n) / O(n²) 等量级，并会在真题中用循环嵌套、递归层数等方式考查时间、空间效率 。

1. 常见时间复杂度及典型示例

记忆窍门：

• • 每多一层完整循环 → 复杂度乘一个 n
• • 折半 / 指数式缩减数据规模 → log n
• • 常数次操作、无循环 → O(1)

2. 用循环嵌套快速估计复杂度

真题 24 年 6 月选择题 12 就给出嵌套循环代码，要求填空并估时间复杂度为 O(n²)（冒泡第一轮移动最大元素） 。

3. 空间复杂度速算

递归栈

• • 深度 d，若每层只保存常数级局部变量 → O(d)
• • 经典例：快速幂深度 log n → O(log n) 的栈空间。
• • 真题“辗转相除法”递归栈深度取决于数值大小，考纲要求能说明其空间消耗 。

判定技巧：只看 “额外申请的新内存/栈帧”，忽略输入本身占用。

4. 典型真题小结

5. 备考要点

1. 1. 先数循环层数，再看循环体是否完全执行（上三角 vs. 全矩形）。
2. 2. 递归→写出递推式，常用主定理或树形展开求解。
3. 3. 空间复杂度牢记三来源：

• • • 动态/静态数组
  • • STL 容器
  • • 递归调用栈

1. 4. 排序、查找、递推类是出题“固定资产”，务必会写其 O 表达式。
2. 5. 考试时若被要求“简单说明理由”，写出循环次数 × 每次耗时即可得分。

二、C++ 异常处理机制入门

只要求 认识 try-catch 结构、能读懂并写出捕捉基本类型的最小代码片段；不考自定义类异常、std::exception 继承链等高级用法。

1. try-catch 结构

try {
    // 可能抛出异常的代码
}
catch (异常类型1 形参) {
    // 针对类型1 的处理
}
catch (异常类型2) {
    // 针对类型2 的处理
}
catch (...) {            // 可选，兜底
    // 未被上面捕捉的任何异常
}

• • 执行流程

1. 1. 1. try 块内遇到 throw 表达式; 立即跳转到匹配的 catch。
   2. 2. 若无匹配且也没有 catch (...) ⇒ 程序终止 (std::terminate)。
   3. 3. 处理完后继续执行 catch 块后面的语句。

2. 抛出 / 捕捉基本类型

#include <bits/stdc++.h>
using namespace std;

void divi(int a,int b){
    if(b==0) throw "div0";      // 抛出 C-风格字符串
    if(b<0)  throw -1;          // 抛出 int
    cout<<a/b<<"\n";
}

int main(){
    try{
        divi(10,0);
    }
    catch(constchar* e){       // 捕捉 char*
        cout<<"Err:"<<e<<"\n";
    }
    catch(int code){            // 捕捉 int
        cout<<"Code:"<<code<<"\n";
    }
    return 0;
}

• • throw 后面可以是 任意表达式，类型决定匹配的 catch。
• • 捕捉基本类型时形参可省名：catch(int){…}。

3. “万能捕捉” catch(...)

try {
    risky();
}
catch (...) {                  // 无形参
    cerr<<"未知异常\n";
}

• • 位置通常放在所有特定 catch 之后；因为匹配范围最大。
• • 捕捉到后如需再次上抛：throw;（空 throw 语法，仅能在 catch 内用一次）。

4. 小贴士与真题要点

5. 一行示例：捕所有异常

try{ foo(); } catch(...){ /* ignore */ }

备考时会让你指出 catch(...) 能捕获包括 int、double、自定义对象在内的 任何类型 异常 —— 选“对”。

📂 三、文件操作与重定向

大多数竞赛与 GESP 真题仅考 文本文件 基本读写与竞赛常用的 freopen 重定向；流式 ifstream / ofstream 需会写最小示例。

1️⃣ freopen —— 把标准流“接”到文件

#include<bits/stdc++.h>
using namespace std;
int main(){
    freopen("in.txt","r",stdin);   // 把 cin/scanf 重定向到 in.txt
    freopen("out.txt","w",stdout); // 把 cout/printf 写入 out.txt
    int x; while(cin>>x) cout<<x*x<<"\n";
}

• • 返回值：nullptr 表示打开失败。
• • 典型真题：给定一段代码，问它将输出定向到哪（24 年 6 月单 13）。

2️⃣ C 风格文本读写：fscanf / fprintf

#include <stdio.h>
int main(){
    FILE *fp = fopen("data.txt","w");
    if(!fp) return 1;
    for(int i=1;i<=3;i++)
        fprintf(fp,"%d\n",i*i);    // 写平方
    fclose(fp);

    fp = fopen("data.txt","r");
    int v;
    while(fscanf(fp,"%d",&v)==1)   // 读回并打印
        printf("%d ",v);
    fclose(fp);
}

• • 格式符与 scanf/printf 完全相同。
• • 返回值：写成功字符数 / 读成功匹配数。
• • 考点：漏写 & / 忘记 fclose。

3️⃣ C++ 流式：ifstream / ofstream

#include<bits/stdc++.h>
using namespace std;
int main(){
    ifstream fin("in.txt");        // 自动以文本模式
    ofstream fout("out.txt");
    int n; fin>>n;
    vector<int> v(n);
    for(int &x:v) fin>>x;

    sort(v.begin(),v.end());
    for(int x:v) fout<<x<<' ';
    // RAII 自动关闭文件
}

重定向替代法

./prog < in.txt > out.txt

无需改代码，可在真题评测或调试时快速切换数据文件。

4️⃣ 常见坑 & 小技巧

5️⃣ 备考速记

1. 1. 单文件 I/O：freopen("in","r",stdin); 写一行搞定。
2. 2. 单行读写：fscanf(fp,"%s",buf); / fprintf(fp,"%d\n",x);。
3. 3. 流式首选：ifstream fin; if(!fin){…}，流与 >> / << 同控制台用法一致。
4. 4. 结束前记得 fclose（或让析构自动收尾），否则数据可能未刷新到磁盘。