复杂度分析CSP-J

💡 核心思想

复杂度分析是评估算法效率的核心工具。时间复杂度衡量算法执行步数随输入规模增长的趋势，空间复杂度衡量额外内存消耗。我们使用大 O 表示法（渐进上界）来描述，忽略常数因子，只关注增长趋势。

🎯 直觉理解

想象你要在一堆书中找一本特定的书。如果书是乱放的，你只能一本一本翻——这是 $O(n)$。如果书是按字母排好的，你可以二分查找——这是 $O(\log n)$。复杂度就是描述"当书的数量翻倍时，找书的时间翻几倍"。

📝 算法流程

1. 理解输入规模 $n$ 的含义
2. 找出基本操作（比较、赋值等）的执行次数
3. 用大 O 表示法取最高阶项，忽略常数
4. 常见复杂度排序：$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n) < O(n!)$

$$T(n) = O(f(n)) \text{ 表示 } \exists c, n_0, \forall n > n_0, T(n) \le c \cdot f(n)$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
// 复杂度估算示例：常见操作的复杂度
int main() {
    int n; cin >> n;
    // O(1) - 直接访问
    int a = n;
    // O(log n) - 二分查找
    vector<int> v(n);
    // O(n) - 线性扫描
    for(int i = 0; i < n; i++) v[i] = i;
    // O(n log n) - 排序
    sort(v.begin(), v.end());
    // O(n^2) - 冒泡排序（不要在竞赛中用）
    // O(2^n) - 枚举子集
    for(int mask = 0; mask < (1 << n); mask++) {
        // 处理子集 mask
    }
    return 0;
}

⚠️ 常见坑点

📚 相关题目