C++ 时间复杂度详解

时间复杂度是衡量算法执行效率的核心指标，描述算法运行时间随输入规模增长的趋势，而非精确时间。

---

一、什么是时间复杂度

时间复杂度（Time Complexity）用 大 O 表示法（Big O Notation） 来描述：当输入规模 $n$ 趋于无穷大时，算法执行次数的上界。

三条核心规则：

规则	说明	示例
保留最高阶项	当 $n\to \infty$ 时，最高阶项主导	$n^2+n\to O(n^2)$
忽略常数系数	大 O 只关心增长趋势	$3n\to O(n)$
加法取最大，乘法保留	多段代码：相加取最大；嵌套：相乘	见下文详解

---

二、如何计算时间复杂度：四步法

---

三、常见时间复杂度代码示例（带详细计算过程）

3.1 O(1) — 常数阶

// 无论 n 多大，只执行一次
int getFirst(vector<int>& arr) {
    return arr[0];  // 1 次基本操作
}
// T(n) = 1 → O(1)

n 的值	执行次数
10	1
100	1
1,000,000	1

---

3.2 O(log n) — 对数阶

// 二分查找：每次查找范围减半
int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;        // O(1)
    while (left <= right) {                       // 循环多少次？
        int mid = left + (right - left) / 2;      // O(1)
        if (arr[mid] == target) return mid;       // O(1)
        else if (arr[mid] < target)
            left = mid + 1;                       // 范围缩小一半
        else
            right = mid - 1;                      // 范围缩小一半
    }
    return -1;
}

计算过程：

• 初始范围大小：$n$
• 第 1 次循环后：$n/2$
• 第 2 次循环后：$n/4$
• 第 k 次循环后：$n/2^k$
• 当 $n/2^k=1$ 时循环结束 → $k={\log }_{2}n$
• 故：O(log n)

---

3.3 O(n) — 线性阶

// 遍历数组：每个元素访问一次
int findMax(vector<int>& arr) {
    int maxVal = arr[0];                    // 1 次
    for (int i = 1; i < arr.size(); i++) {  // 循环 n-1 次
        if (arr[i] > maxVal)                // n-1 次比较
            maxVal = arr[i];                // 最多 n-1 次赋值
    }
    return maxVal;                          // 1 次
}
// T(n) = 1 + (n-1) + (n-1) + 1 = 2n ≈ O(n)

---

3.4 O(n log n) — 线性对数阶

// 归并排序：每层 O(n)，共 log n 层
void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;                   // O(1)
    int mid = left + (right - left) / 2;         // O(1)
    mergeSort(arr, left, mid);                   // 递归左半
    mergeSort(arr, mid + 1, right);              // 递归右半
    merge(arr, left, mid, right);                // O(n) 合并
}

计算过程 — 递归树分析法：

• 递归深度：${\log }_{2}n$ 层
• 每层合并操作总和：$O(n)$
• 总时间 = 层数 × 每层代价 = $O(n\log n)$

---

3.5 O(n²) — 平方阶

// 双重循环：外层 n 次，内层 n 次
void printPairs(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {         // 执行 n 次
        for (int j = 0; j < n; j++) {     // 每次执行 n 次
            cout << arr[i] << "," << arr[j] << endl;  // n × n 次
        }
    }
}
// T(n) = n × n = n² → O(n²)

⚠️ 注意区分：内层循环范围从 0 开始时才是 $n^2$，若内层从 i+1 开始则变为 $n(n-1)/2$ → 仍然是 O(n²)（系数被忽略）。

// 内层范围递减 — 仍是 O(n²)
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)  // 执行 n-1, n-2, ..., 1 次
        doSomething();
// T(n) = (n-1) + (n-2) + ... + 1 = n(n-1)/2 = 0.5n² - 0.5n → O(n²)

---

3.6 O(2ⁿ) — 指数阶

// 斐波那契递归（朴素版）
int fib(int n) {
    if (n <= 1) return n;           // O(1)
    return fib(n - 1) + fib(n - 2); // 每次调用分裂为两个子问题
}

调用次数：$T(n)=T(n-1)+T(n-2)+O(1)\approx O(2^n)$
每层节点数倍增，是一棵接近满的二叉树。

---

3.7 O(n!) — 阶乘阶

// 全排列生成（回溯法）
void permute(vector<int>& nums, int start, vector<vector<int>>& res) {
    if (start == nums.size()) {
        res.push_back(nums);  // 找到一个排列
        return;
    }
    for (int i = start; i < nums.size(); i++) {  // 每层可选数递减
        swap(nums[start], nums[i]);
        permute(nums, start + 1, res);            // 递归
        swap(nums[start], nums[i]);
    }
}
// 第 k 层有 (n-k) 个分支，总共 n × (n-1) × ... × 1 = n! → O(n!)

---

四、时间复杂度增长对比

实际运行时间估算（假设每次操作 1ns）

输入规模 n	O(log n)	O(n)	O(n log n)	O(n²)	O(2ⁿ)
10	3ns	10ns	33ns	100ns	1μs
100	7ns	100ns	664ns	10μs	4×10¹³ 年 😱
1,000	10ns	1μs	10μs	1ms	∞
10⁶	20ns	1ms	20ms	17 分钟	∞
10⁹	30ns	1s	30s	32 年	∞

---

五、多段代码的时间复杂度分析

5.1 顺序结构：加法取最大

void process(vector<int>& arr) {
    // 代码块 A：O(n)
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";

    // 代码块 B：O(n²)
    for (int i = 0; i < arr.size(); i++)
        for (int j = 0; j < arr.size(); j++)
            cout << arr[i] + arr[j] << " ";

    // 代码块 C：O(n)
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i] * 2 << " ";
}
// 总时间 = O(n) + O(n²) + O(n) = O(n²)（取最大）

---

5.2 循环嵌套：乘法

for (int i = 0; i < n; i++) {         // O(n)
    for (int j = 0; j < m; j++) {     // O(m)
        cout << i + j;                // O(1)
    }
}
// 总时间 = O(n) × O(m) × O(1) = O(n × m)
// 若 m = n，则 O(n²)

---

5.3 混合结构示例

void example(int n, int m) {
    // 部分 1：嵌套循环 O(n × m)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            doA();                          // O(1)

    // 部分 2：单循环 O(n)
    for (int i = 0; i < n; i++)
        doB();                              // O(1)

    // 部分 3：递归 O(2ⁿ)
    fibonacci(n);
}
// 总时间 = O(n×m + n + 2ⁿ) = O(2ⁿ)

经验法则： 有递归看递归，没递归看嵌套最深层，多段代码取最大。

---

六、递归算法的时间复杂度

6.1 主定理（Master Theorem）

对于递推式 $T(n)=a\cdot T(n/b)+f(n)$：

条件	时间复杂度
$f(n)=O(n^{{\log }_{b}a-ϵ})$	$O(n^{{\log }_{b}a})$
$f(n)=\Theta (n^{{\log }_{b}a})$	$O(n^{{\log }_{b}a}\log n)$
$f(n)=\Omega (n^{{\log }_{b}a+ϵ})$	$O(f(n))$

6.2 典型递归案例速查

算法	递推式	时间复杂度
二分查找	$T(n)=T(n/2)+O(1)$	O(log n)
归并排序	$T(n)=2T(n/2)+O(n)$	O(n log n)
快速排序（平均）	$T(n)=2T(n/2)+O(n)$	O(n log n)
快速排序（最坏）	$T(n)=T(n-1)+O(n)$	O(n²)
斐波那契（朴素）	$T(n)=T(n-1)+T(n-2)+O(1)$	O(2ⁿ)
二分查找变体	$T(n)=T(n/2)+O(n)$	O(n)

---

七、C++ STL 常见操作时间复杂度

容器操作复杂度一览

STL 算法复杂度速查

算法	时间复杂度	说明
sort()	O(n log n)	内省排序（快排+堆排+插入排序混合）
binary_search()	O(log n)	二分查找
find() / count()	O(n)	线性遍历
lower_bound() / upper_bound()	O(log n)	基于二分查找
next_permutation()	O(n)	每次调用
reverse()	O(n)	线性遍历
make_heap()	O(n)	建堆
push_heap() / pop_heap()	O(log n)	堆调整
nth_element()	O(n) 平均	快排分区

---

八、常见误区与易错点

8.1 误区一：以为循环减半就是 O(log n)

// ❌ 错误：这是 O(n)！
for (int i = 0; i < n; i += 2)  // 执行 n/2 次
    doSomething();
// n/2 ∈ O(n)，减半 ≠ 对半分割

// ✅ 正确：这才是 O(log n)
for (int i = 1; i < n; i *= 2)  // i: 1,2,4,8,... → 执行 log n 次
    doSomething();

8.2 误区二：多循环一定嵌套

// 三个独立循环 → O(n + m + k)，不是 O(n³)
for (int i = 0; i < n; i++) doA();
for (int j = 0; j < m; j++) doB();
for (int k = 0; k < kMax; k++) doC();
// T(n) = n + m + kMax → O(n + m + kMax)

8.3 误区三：忽略隐藏的循环

// string 拼接：看似 O(1)，实则 O(m)
string s = "";
for (int i = 0; i < n; i++)
    s += "a";           // 每次 += 是 O(s.length())，总计 O(n²)！
// 修正：使用 vector<char> 或 string::reserve + push_back

8.4 误区四：递归看起来很简短 ≠ 复杂度低

void dfs(int n) {
    if (n == 0) return;
    dfs(n - 1);   // T(n) = T(n-1) + O(1) → O(n)
    dfs(n - 1);   // T(n) = 2T(n-1) + O(1) → O(2ⁿ) ← 多一条语句，天壤之别
}

---

九、复杂度分析决策流程

---

十、速记口诀

「常对线，线性对，平方指数阶乘尾」

复杂度	口诀	记忆点
O(1)	常数阶	一行代码，不依赖 n
O(log n)	对数阶	每次减半，i *= 2
O(n)	线性阶	一层完整循环
O(n log n)	线性对数阶	分治+合并，快排/归并
O(n²)	平方阶	双层嵌套完整循环
O(n³)	立方阶	三层嵌套，Floyd 算法
O(2ⁿ)	指数阶	每次递归分裂两个子问题
O(n!)	阶乘阶	全排列，暴力枚举