GESP 6级 · 时间复杂度

💡 为什么重要

时间复杂度是评价算法好坏的核心标准。GESP 6级考试几乎每道编程题都会问"分析时间复杂度"。更重要的是，理解它能帮你在面对问题时选择正确的解法。比如 n=100000 时，O(n²) 需要 100 亿次操作（超时），而 O(n log n) 只需约 170 万次（瞬间完成）。

📖 前置知识

for 循环和 while 循环
函数的定义和调用
基本的递归概念（可选但有帮助）

🔍 什么是"时间复杂度"？

时间复杂度不是程序实际运行了多少秒，而是程序的执行次数随输入规模 n 增长的趋势。我们用大 O 符号表示，忽略常数和低阶项。

核心思想：忽略常数系数和低阶项

执行了 3n 次 → O(n)（忽略系数 3）
执行了 2n + 5 次 → O(n)（忽略系数 2 和常数 5）
执行了 n² + n 次 → O(n²)（忽略低阶项 n）

📐 常见复杂度从小到大

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

O(1) → 常数时间：直接取值，与n无关
O(log n) → 对数时间：二分查找
O(n) → 线性时间：遍历一遍
O(n log n) → 线性对数：归并排序
O(n²) → 平方时间：双重循环
O(2ⁿ) → 指数时间：暴力枚举子集
O(n!) → 阶乘时间：全排列

★ n=100000 时的大致操作次数：
O(1) ≈ 1次
O(log n) ≈ 17次
O(n) ≈ 100,000次
O(n log n) ≈ 1,700,000次
O(n²) ≈ 10,000,000,000次（超时！）

💻 代码与复杂度对应关系

📝 O(1) — 常数时间

// O(1): 不管n多大，固定操作次数
int getFirst(int arr[], int n) {
    return arr[0];      // 直接取值，1次操作
}

bool isEven(int n) {
    return n % 2 == 0;  // 一次取余和比较
}

📝 O(n) — 线性时间：单层循环

// O(n): 循环体执行约n次
int findMax(int arr[], int n) {
    int maxVal = arr[0];
    for (int i = 1; i < n; i++) {  // 循环n-1次
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
    }
    return maxVal;
}

📝 O(n²) — 平方时间：双重嵌套循环

// O(n²): 外层n次 × 内层n次
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 1; j++) {
            if (arr[j] > arr[j+1]) {
                int t = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = t;
            }
        }
    }
}

📝 O(log n) — 对数时间：每次排除一半

// O(log n): 二分查找
int binarySearch(int arr[], int n, int target) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {             // 循环约log₂(n)次
        int mid = (lo + hi) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
        // 每次范围减半：n → n/2 → n/4 → ... → 1
    }
    return -1;
}

📝 O(n log n) — 线性对数时间

// O(n log n): 外层n次 × 内层每次减半log(n)次
void someOperation(int n) {
    for (int i = 0; i < n; i++) {  // 外层n次
        int x = n;
        while (x > 1) {            // 内层每次减半
            x /= 2;                 // 约log(n)次
        }
    }
    // 总计：n × log(n) = O(n log n)
}
// 典型代表：归并排序、快速排序（平均）

📝 O(2ⁿ) — 指数时间：暴力枚举

// O(2ⁿ): 枚举所有子集（每个元素选或不选）
void printAllSubsets(int arr[], int n) {
    for (int mask = 0; mask < (1 << n); mask++) {
        // mask从0到2ⁿ-1，共2ⁿ次
        cout << "{ ";
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) cout << arr[i] << " ";
        }
        cout << "}" << endl;
    }
    // n=20时约100万次，n=30时约10亿次！
}

🔍 分析技巧

找循环：看循环执行多少次，嵌套循环次数相乘
忽略常数：3n → O(n)，n²/2 → O(n²)
取最高阶：n² + n → O(n²)
二分/减半：每次减半 → O(log n)
STL函数：sort() 是 O(n log n)，find() 在 vector 上是 O(n)

⚠️ 易错点

把 O(2n) 写成 O(2n)：正确是 O(n)！常数系数要忽略
分不清 O(n) 和 O(n²)：两层嵌套循环就是 O(n²)
误认为递归都是 O(2ⁿ)：尾递归可以是 O(n)，二分递归是 O(log n)
忘记 sort 的复杂度：C++ 的 sort 是 O(n log n)，不是 O(n²)
忽略"取最高阶"原则：O(n³ + n² + n) = O(n³)，只看最大的那项

🎯 练习建议

入门：写出以下代码的时间复杂度：单层循环、双重循环、三重循环
进阶：分析冒泡排序、选择排序、插入排序的时间复杂度
挑战：同一道题用 O(n²) 暴力和 O(n log n) 排序实现，对比运行时间
思考：为什么 n=10⁵ 时 O(n²) 会超时但 O(n log n) 不会？
画图：用表格画出不同 n 值下各复杂度的操作次数

← 上一个：链表概念 📖 返回主目录已是最后一个