算法复杂度概念梳理

---

一、基本概念

1. 大O表示法

• 表示最坏情况下的增长率（忽略常数、低阶项）
• 例：( $T(n) = 3n^2 + 2n + 1 ) → ( O(n^2)$)

2. 常见复杂度（从快到慢）

• $O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n) < O(n!)$

---

二、多项式复杂度

1. ($O(1)$) —— 常数时间

特征：执行次数与输入规模 n 无关

代码结构：

int a = arr[0];           // 一次操作
int b = a * 2 + 5;        // 几次运算，仍 O(1)

2. ($O(n)$) —— 线性时间

特征：单层循环，循环次数与 n 成正比

代码结构：

for(int i = 0; i < n; i++) {
    // O(1) 操作
}

3. ($O(n^2)$) —— 平方时间

特征：双重循环，内外都与 n 相关

代码结构：

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        // O(1) 操作
    }
}

变体（仍是 ($O(n^2)$)）：

for(int i = 0; i < n; i++) {
    for(int j = i; j < n; j++) {  // 约 n²/2 次
        // ...
    }
}

4. ($O(n^3)$) —— 立方时间

特征：三重循环

for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
        for(int k = 0; k < n; k++)
            // O(1)

5. 多项式复杂度的加法 vs 乘法

• 顺序执行：($O(n) + O(n^2) = O(n^2)$)（取最高阶）
• 嵌套执行：($O(n) \times O(n) = O(n^2)$)

---

三、对数复杂度 ($O(\log n)$)

特征

• 每次循环将问题规模减半（或变为固定比例）
• 常见于二分法、倍增法

代码结构 1：循环除以 2

int i = n;
while(i > 0) {
    // O(1) 操作
    i /= 2;          // 关键：每次减半
}

分析：n → n/2 → n/4 → … → 1，共 ($\log_2 n$) 步

代码结构 2：循环乘以 2

for(int i = 1; i < n; i *= 2) {
    // O(1) 操作
}

分析：1, 2, 4, 8, …, 共 ($\log_2 n$) 步

代码结构 3：二分查找

int l = 0, r = n-1;
while(l <= r) {
    int mid = (l+r)/2;
    if(arr[mid] == target) return mid;
    else if(arr[mid] < target) l = mid+1;
    else r = mid-1;
}

---

四、($O(n \log n)$) 复杂度

特征

• 外层线性，内层对数
• 或分治算法（归并排序、快速排序的期望）

代码结构 1：n × log n

for(int i = 0; i < n; i++) {      // O(n)
    int j = n;
    while(j > 0) {                // O(log n)
        // O(1)
        j /= 2;
    }
}

代码结构 2：埃氏筛

bool isPrime[n+1];
fill(isPrime, isPrime+n+1, true);
for(int i = 2; i <= sqrt(n); i++) {     // 外层 ~√n
    if(isPrime[i]) {
        for(int j = i*i; j <= n; j += i) {  // 内层总次数 ~ n log log n
            isPrime[j] = false;
        }
    }
}

复杂度：( $O(n \log \log n)$ ) —— 属于 ( $O(n \log n)$ ) 级别

代码结构 3：归并排序

每次分两半，深度 ($\log n$)，每层合并 ( $O(n)$ )，总 ( $O(n \log n)$ )

---

五、指数复杂度 ( $O(2^n)$ )

特征

• 每层递归分成两个子问题
• 常见于暴力搜索、递归枚举子集

代码结构：递归枚举子集

void dfs(int idx, int n) {
    if(idx == n) return;
    // 选或不选两种选择
    dfs(idx+1, n);   // 不选
    dfs(idx+1, n);   // 选
}

调用次数：($2^n$)

另一种：斐波那契递归（未优化）

int fib(int n) {
    if(n <= 1) return n;
    return fib(n-1) + fib(n-2);  // 两个递归调用
}

复杂度 ( $O(2^n)$ )（实际约 ( $\phi^n$ )，以1.618为底）