GESP 七级 · GESP 202403 C++ 七级 第 11 题

下面 schedule 函数的时间复杂度为（ ）。

#include <algorithm>
using namespace std;
struct activity {
    int id, start, end;
};
bool compare(activity a, activity b) {
    return a.end < b.end;
}
int schedule(int n, activity * p) {
    sort(p, p + n, compare);
    int cnt = 0, end = 0;
    for (int i = 0; i < n; i++) {
        if (p[i].start >= end) {
            end = p[i].end;
            cnt++;
        }
    }
    return cnt;
}

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】排序（自定义比较器）｜时间复杂度分析｜线性扫描

1. 🎯 考纲定位

• 本题落在 GESP 七级「算法实现」模块，考查对 STL 排序 + 线性扫描的综合运用。命题人把「sort 的复杂度」和「循环复杂度」拆开，卡在多数考生只会背结论、不会拆解步骤的弱点上。

2. 🧠 解题思维

• 先看到 sort(p, p+n, compare)，这是 n 个元素按自定义规则排序，复杂度 O(n log n)。
• 之后 for (int i=0;i<n;i++) 是单趟线性扫描，每次只做常数比较与赋值，复杂度 O(n)。
• 排序主导整体复杂度，故答案为 O(n log n)。

3. 🪤 陷阱拆解

• 选项 A 把循环误当主导，忽略了 sort 的 O(n log n)；选项 D 把排序想成 O(n^2)，混淆了选择排序与 STL 的 O(n log n)。
• 绝对化表述「时间复杂度为」要求唯一答案，若只背结论而不理解 sort 的渐进行为，必掉坑。
• 最阴险的细节：compare 函数虽影响排序结果，但不影响复杂度，命题人借此检验你是否会因「自定义比较器」而过度思考。

4. 🔄 反命题思维

• 若把 sort 换为选择排序，整体仍是 O(n^2)，答案会变；若去掉 sort，直接按输入顺序扫描，则复杂度退化为 O(n)，但算法不再正确。
• 刷到类似题时，先问自己「命题人想考我哪一步的复杂度？」——是排序、循环，还是两者叠加。
• 记住：复杂度分析永远要逐行拆解，不能只看最外层。