一、核心概念：大 O 记号（渐进时间复杂度）

在 408 中，我们主要使用大 O 表示法，它衡量的是算法在最坏情况下的执行效率界限。

计算三大铁律（抓大头，去零头）：
1. 只保留最高阶项： $O (3 n^{2} + 5 n + 10) \to O (n^{2})$ 。
2. 常数系数化为 1： $O (5 n) \to O (n)$ ， $O (10000) \to O (1)$ 。
3. 加法法则（串行代码）： $O (f (n)) + O (g (n)) = O (max (f (n), g (n)))$ 。谁大听谁的。
4. 乘法法则（嵌套循环）： $O (f (n)) \times O (g (n)) = O (f (n) \times g (n))$ 。内外层相乘。

二、时间复杂度（Time Complexity）

看什么？ 找代码里执行次数最多的那条语句（通常在最内层循环），看它的执行次数和问题规模 $n$ 的数学关系。

常见量级（必须背诵，按从快到慢排序）：

$O (1) < O (lo g n) < O (n) < O (n lo g n) < O (n^{2}) < O (n^{3}) < O (2^{n}) < O (n!)$

$O (1)$ 常数阶
- 特征：没有循环，或者循环次数是常数。
- 例子：基础的加减乘除、数组随机访问 a[i]、常数次循环 for(int i=0; i<100; i++)。
$O (lo g n)$ 对数阶（408 最爱考的拉分项）
- 特征：循环变量每次乘以/除以一个常数，呈指数级逼近终点。
- 例子：二分查找、二叉树的遍历（树高）。
- 代码：while(i <= n) { i = i * 2; }
$O (n)$ 线性阶
- 特征：单层循环，步长为常数（通常为 1）。
- 例子：遍历一维数组、链表查找。
- 代码：for(int i=0; i<n; i++) { ... }
$O (n lo g n)$ 线性对数阶
- 特征：外层是一个 $O (n)$ 的循环，内层是一个 $O (lo g n)$ 的循环。
- 例子：快速排序、归并排序、堆排序的平均情况。这是比较排序算法的时间下限。
$O (n^{2})$ 平方阶
- 特征：两层嵌套循环。
- 例子：冒泡排序、插入排序、选择排序、遍历二维矩阵。
$O (2^{n})$ / $O (n!)$ 指数阶/阶乘阶
- 特征：通常见于暴力穷举。如果在 408 算法大题里你写出了这种复杂度，基本意味着方法全错，只能拿 1-2 分的代码卷面分。

三、空间复杂度（Space Complexity）

看什么？ 为了运行这个算法，除了题目原本给你的输入数据外，你额外申请了多少内存空间？

$O (1)$ 原地工作（In-place）
- 特征：只定义了几个额外的局部变量（如 int i, j, temp;）。无论 $n$ 有多大，这几个变量占用的字节数不变。
- 408 要求：只要题目说“空间复杂度尽可能高效”，潜台词就是逼你写 $O (1)$ 。
$O (n)$ 线性空间
- 特征：为了处理 $n$ 个数据，你 malloc（或者 new）了一个大小为 $n$ 的辅助数组。
$O (n^{2})$ 平方空间
- 特征：开辟了大小为 $n \times n$ 的二维数组（如：图的邻接矩阵）。
【隐蔽考点】递归的函数调用栈空间
- 注意：递归代码虽然没有明显定义数组，但每次递归系统都要压栈（保存局部变量和返回地址）。
- 计算：空间复杂度 = 递归树的深度。如果递归深度是 $n$ ，空间复杂度就是 $O (n)$ 。

四、 408 算法题“骗分”兵法

既然你的策略是“先拿基础分”，那这几条原则你必须刻在骨子里：

时空互换原则：时间和空间往往不可兼得。408 大题如果卡住了，绝对不要死磕双优。立刻开一个新数组（牺牲空间，变成 $O (n)$ ），用最简单直接的 $O (n)$ 循环把流程跑通。13 分你至少能拿 8-10 分！
暴力出奇迹：看到不懂的题，先写两层 for 循环暴力匹配。 $O (n^{2})$ 往往是所有题目的保底解法。
不要在考卷上写死循环：即使逻辑不完美，你的 while 和 for 必须有明确的退出条件（比如 i < n），否则直接 0 分。

当数组 A 被当作参数传进 FindMedian 函数的那一刻，它就不再是一个完整的数组了，它退化成了一个指向数组第一个元素的指针（本质上变成了 int *A）。在常见的 64 位系统下，不管你这个数组里装了 5 个数还是 5 万个数，一个指针变量永远只占 8 个字节。那么 sizeof(A) 永远等于 8，sizeof(A[0]) 是一个整型占 4 个字节。算出来的 $n$ 永远是 $8/4 = 2$ 。你的程序跑两步直接就结束了。

408算法大题时间与空间复杂度计算通用指南

是什么

定义：算法的时间复杂度 $T (n)$ 是衡量算法运行时间随数据规模 $n$ 增长的渐进趋势；空间复杂度 $S (n)$ 是衡量算法执行过程中占用的 额外内存空间 随 $n$ 增长的渐进趋势。两者均使用大 $O$ 记号（Big-O）表示。
大白话：时间复杂度看“代码执行了多少次基本操作”，空间复杂度看“除了原输入数据外，额外申请了多少变量或递归栈空间”。

核心内容

1. 时间复杂度 $T (n)$ 的通用计算方法

计算核心：找到代码中执行次数最多的基本语句（通常是最内层循环），计算其随数据规模 $n$ 增长的累计执行次数 $f (n)$ ，取最高阶项并忽略常数系数。

常见代码结构的计算规律

① 单重循环与简单累加 $\to O (n)$

int sum = 0;
for (int i = 0; i < n; i++) { // 循环执行 n 次
    sum += A[i];             // 基本语句
}

次数： $f (n) = n$
复杂度： $O (n)$

② 多重嵌套循环 $\to O (n^{2})$ 或 $O (n^{3})$

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) { // 外层 i=0 时内层 n-1 次，i=1 时 n-2 次...
        // 基本语句
    }
}

次数： $f (n) = (n - 1) + (n - 2) + \dots + 1 = \frac{n ( n - 1 )}{2} = \frac{1}{2} n^{2} - \frac{1}{2} n$
原则：忽略低阶项与常数系数，取最高阶 $n^{2}$ ，得到 $O (n^{2})$ 。

③ 变量翻倍/减半循环 $\to O (lo g n)$

int i = 1;
while (i < n) {
    i = i * 2; // 每次乘以 2
}

次数：设执行 $k$ 次，则 $2^{k} \geq n ⟹ k = lo g_{2} n$
复杂度：忽略对数底数，统一记为 $O (lo g n)$ 。

④ 递归分治结构（Master 定理 / 递推树）

双侧分治（如完全快速排序、归并排序）：

每次把规模为 $n$ 的问题拆成 2 个规模为 $n /2$ 的子问题，本层处理耗时 $O (n)$ 。

$T (n) = 2 T (n /2) + O (n)$

递归树共有 $lo g_{2} n$ 层，每层总工作量为 $n$ ，总时间为 $n \times lo g_{2} n ⟹$ == $O (n lo g n)$ ==。
单侧减半（如快速选择 QuickSelect、二分查找）：

每次把规模为 $n$ 的问题丢弃一半，只保留 1 个规模为 $n /2$ 的子问题，本层处理耗时 $O (n)$ 。

$T (n) = T (n /2) + O (n)$

计算等比数列累加： $n + \frac{n}{2} + \frac{n}{4} + \dots + 1 = n (\frac{1}{1 - 1/2}) = 2 n ⟹$ == $O (n)$ ==。

2. 空间复杂度 $S (n)$ 的通用计算方法

计算核心：只计算算法在运行过程中“额外申请的内存空间”，原输入数组/数据占用的内存空间不计入。

常见空间开销来源

① 局部简单变量 $\to O (1)$

int low = 0, high = n - 1, temp; // 只使用了常数个局部变量

无论 $n$ 是 10 还是 100 万，辅助变量个数恒定，空间复杂度为 $O (1)$ 。

② 辅助数组/哈希表 $\to O (n)$

int *B = (int *)malloc(n * sizeof(int)); // 申请了与 n 等大的辅助数组

申请的额外内存空间与输入规模 $n$ 成正比，空间复杂度为 $O (n)$ 。

③ 函数递归调用栈（最易遗漏点 ⚠️）

递归调用的本质是利用系统栈保存每一层的函数局部变量和返回地址。

==递归栈空间 = 递归树的最大深度 $\times$ 每层栈帧大小==。
例 1：单路线性递归（如递归求阶乘、单链表递归）

递归深度为 $n$ ，系统栈中同时保存 $n$ 个函数帧 $⟹ O (n)$ 。
例 2：双侧分治递归（如快速排序、二叉树树高）

平均情况下，递归树高度为 $lo g_{2} n$ ，系统栈中最多同时保存 $lo g_{2} n$ 个函数帧 $⟹$ == $O (lo g n)$ ==。

（注：最坏情况下快排树退化为单链，深度为 $n ⟹ O (n)$ ）。

例题

题目：指出 2016 真题中“集合划分为 $A_{1}, A_{2}$ 且 $∣ S_{1} - S_{2} ∣$ 最大”的暴力全排序算法与最优快速选择算法（QuickSelect）的平均时间复杂度和空间复杂度，并说明依据。
分析：比较全排序算法（双侧递归）与单侧划分算法（QuickSelect）在步数规约和栈空间占用上的差异。
答案：
- 全排序方案：平均时间复杂度为 == $O (n lo g n)$ ==，依据为快速排序递归树深度为 $O (lo g n)$ 且每层处理 $O (n)$ 次；空间复杂度为 == $O (lo g n)$ ==，依据为系统递归调用栈的深度。
- 快速选择方案（最优）：平均时间复杂度为 == $O (n)$ ==，依据为单侧划分比较次数收敛于等比数列 $n + \frac{n}{2} + \frac{n}{4} + \dots = 2 n$ ；空间复杂度为 == $O (1)$ ==，依据为采用 while 循环迭代实现，无递归栈开销，仅占用常数个辅助变量。

⚠️ 易错点

Warning

混淆输入空间与额外空间 → 题目给出的输入数组 int A[] 本身占用的内存空间不计入空间复杂度，只有代码里额外 malloc 的内存或系统递归栈才算！

忽视递归栈开销 → 凡是写了递归函数（如 QuickSort），哪怕一行 malloc 都没写，空间复杂度也绝不能写 $O (1)$ ，至少是 == $O (lo g n)$ 的栈空间==！

混淆单侧递归与双侧递归 → 完全快速排序是对左右两边都递归处理（ $2 \times \frac{n}{2}$ ），时间为 $O (n lo g n)$ ；快速选择（QuickSelect）只对包含目标点的单侧递归/迭代（ $\frac{n}{2}$ ），时间复杂度收敛为 == $O (n)$ ==。

把最坏情况当成平均情况 → 快速排序在最坏情况（如完全有序）下时间复杂度会退化为 $O (n^{2})$ ，但在 408 答题中第 (3) 问若无明确说明，默认书写并推导平均复杂度。

Quartz 4

Explorer

时间And空间复杂度分析

一、核心概念：大 O 记号（渐进时间复杂度）

二、时间复杂度（Time Complexity）

三、空间复杂度（Space Complexity）

四、 408 算法题“骗分”兵法

408算法大题时间与空间复杂度计算通用指南

是什么

核心内容

1. 时间复杂度 $T (n)$ 的通用计算方法

常见代码结构的计算规律

① 单重循环与简单累加 $\to O (n)$

② 多重嵌套循环 $\to O (n^{2})$ 或 $O (n^{3})$

③ 变量翻倍/减半循环 $\to O (lo g n)$

④ 递归分治结构（Master 定理 / 递推树）

2. 空间复杂度 $S (n)$ 的通用计算方法

常见空间开销来源

① 局部简单变量 $\to O (1)$

② 辅助数组/哈希表 $\to O (n)$

③ 函数递归调用栈（最易遗漏点 ⚠️）

例题

⚠️ 易错点

Graph View

Table of Contents

Quartz 4

Explorer

时间And空间复杂度分析

一、 核心概念：大 O 记号（渐进时间复杂度）

二、 时间复杂度（Time Complexity）

三、 空间复杂度（Space Complexity）

四、 408 算法题“骗分”兵法

408算法大题时间与空间复杂度计算通用指南

是什么

核心内容

1. 时间复杂度 T(n) 的通用计算方法

常见代码结构的计算规律

① 单重循环与简单累加 →O(n)

② 多重嵌套循环 →O(n2) 或 O(n3)

③ 变量翻倍/减半循环 →O(logn)

④ 递归分治结构（Master 定理 / 递推树）

2. 空间复杂度 S(n) 的通用计算方法

常见空间开销来源

① 局部简单变量 →O(1)

② 辅助数组/哈希表 →O(n)

③ 函数递归调用栈（最易遗漏点 ⚠️）

例题

⚠️ 易错点

Graph View

Table of Contents

一、核心概念：大 O 记号（渐进时间复杂度）

二、时间复杂度（Time Complexity）

三、空间复杂度（Space Complexity）

1. 时间复杂度 $T (n)$ 的通用计算方法

① 单重循环与简单累加 $\to O (n)$

② 多重嵌套循环 $\to O (n^{2})$ 或 $O (n^{3})$

③ 变量翻倍/减半循环 $\to O (lo g n)$

2. 空间复杂度 $S (n)$ 的通用计算方法

① 局部简单变量 $\to O (1)$

② 辅助数组/哈希表 $\to O (n)$