GESP 6级 · 时间复杂度

📖概念讲解

时间复杂度是衡量算法运行时间随输入规模增长的趋势，用大 O 记号表示。核心思路：只看最高阶项，忽略常数和低阶项。

常见时间复杂度从小到大：

复杂度	名称	示例（n=100万时）
O(1)	常数	1 次操作
O(log n)	对数	~20 次
O(n)	线性	~100万次
O(n log n)	线性对数	~2000万次
O(n²)	平方	~1万亿次 ⚠️ 超时
O(2ⁿ)	指数	💀 爆炸

💡 核心规则：单层循环 = O(n)，嵌套两层 = O(n²)，每次折半 = O(log n)。考试常考"给代码判断复杂度"。

💻代码示例

#include <iostream>
using namespace std;
int main() {
    int n = 1000;
    // ① O(1) — 常数时间，无论n多大都执行1次
    int x = 42;            // 直接赋值，1步搞定
    cout << x << endl;
    // ② O(n) — 单层循环，执行n次
    for(int i = 0; i < n; i++) { // 循环n次，每次O(1)
        cout << i << " ";  // 输出操作也是O(1)
    }
    // ③ O(n²) — 两层嵌套循环
    for(int i = 0; i < n; i++)       // 外层n次
        for(int j = 0; j < n; j++) // 内层也n次 → n×n = n²
            cout << i*n+j << " "; // 所以冒泡排序是O(n²)
    // ④ O(log n) — 每次折半，经典二分查找
    int lo=0, hi=n, mid;
    while(lo < hi) {         // 每次搜索范围减半
        mid = (lo+hi)/2;     // 取中间值
        lo = mid+1;          // 砍掉一半，所以只跑log₂n次
    }
    // ⑤ O(n log n) — 归并排序/快排平均
    // 拆分log n层 × 每层合并n次 = n log n
    cout << "\n# 输出: 42";
    return 0;
}

# 输出: 42

🧩互动小测

Q1：下面代码的时间复杂度是？

for(int i=0; i

Q2：n=100 时，O(n²) 大约执行多少次？

Q3：GESP C++ 考试中 n=10⁵ 时，通常哪种复杂度能通过？

🏋️动手练一练

📝 编程练习

给定一个 vector<int> a，实现以下操作并分析各自的时间复杂度：
1. 从头到尾遍历一次，找出最大值
2. 用二分查找在有序数组中查找一个数
3. 将两个长度均为 n 的有序数组合并成一个有序数组

要求：在注释中标注每段代码的时间复杂度。

参考答案：

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

// ① 找最大值：遍历一遍 → O(n)
int findMax(vector<int>& a) {
    int mx = a[0];               // 初始化为第一个元素
    for(int i = 1; i < a.size(); i++)  // 从第2个开始比较
        if(a[i] > mx) mx = a[i]; // 更新最大值
    return mx;                   // 总共n-1次比较 → O(n)
}

// ② 二分查找：每次折半 → O(log n)
bool binarySearch(vector<int>& a, int target) {
    int lo = 0, hi = a.size()-1; // 搜索区间 [lo, hi]
    while(lo <= hi) {           // 区间不为空就继续
        int mid = lo + (hi-lo)/2; // 防溢出写法
        if(a[mid] == target) return true;
        else if(a[mid] < target) lo = mid+1; // 右半边
        else hi = mid-1;         // 左半边
    }
    return false;                // O(log n)
}

// ③ 合并两个有序数组：每步选一个 → O(n)
vector<int> merge(vector<int>& a, vector<int>& b) {
    vector<int> res;
    int i=0, j=0;                // 双指针
    while(i < a.size() && j < b.size()) {
        if(a[i] <= b[j]) res.push_back(a[i++]); // 小的先入
        else res.push_back(b[j++]);
    }
    while(i < a.size()) res.push_back(a[i++]); // 剩余直接追加
    while(j < b.size()) res.push_back(b[j++]);
    return res;                  // 总共最多n步 → O(n)
}

int main() {
    vector<int> a = {1,3,5,7,9};
    cout << "最大值: " << findMax(a) << endl;
    cout << "查找5: " << (binarySearch(a,5)?"找到":"没找到") << endl;
    vector<int> b = {2,4,6,8};
    vector<int> c = merge(a,b);
    for(int x:c) cout << x << " ";
    cout << endl;
    return 0;
}

要点：找最大值 O(n)，二分 O(log n)，合并 O(n)。考试中要能快速识别循环层数和每层的执行次数。

📝易错点提醒

嵌套循环不一定 O(n²)：如果内层循环次数依赖外层（如 for j=i），实际是 n(n-1)/2，仍然是 O(n²)——因为忽略常数和低阶项。
递归看展开次数：斐波那契递归 f(n)=f(n-1)+f(n-2) 是 O(2ⁿ)，因为每层展开2个分支。
数组操作：push_back 是均摊 O(1)，但 insert 在中间插入是 O(n)（要移动元素）。
sort 默认快排：C++ sort() 是 O(n log n)，别记成 O(n²)。但手写冒泡是 O(n²)。
考试秒杀技巧：看到"嵌套两层到n"→ O(n²)；"每次折半"→ O(log n)；"for(int i=0;i<n;i++)单层"→ O(n)。

📘时间复杂度

📖概念讲解

💻代码示例

🧩互动小测

Q1：下面代码的时间复杂度是？

Q2：n=100 时，O(n²) 大约执行多少次？

Q3：GESP C++ 考试中 n=10⁵ 时，通常哪种复杂度能通过？

🏋️动手练一练

📝 编程练习

📝易错点提醒