一、基本概念与符号说明

时间复杂度（Time Complexity）：用于衡量算法在执行过程中所需的基本操作次数随输入规模 (n) 增长的趋势。通常关注其渐近行为，忽略常数项和低阶项的影响。

空间复杂度（Space Complexity）：指算法在运行过程中所占用的额外内存空间（不包含输入数据本身）随着输入规模 (n) 的增长情况。

渐近记号（Asymptotic Notation）：

• (f(n) = O(g(n))) — 上界：存在常数 (c > 0, n_0)，使得当 (n ≥ n_0) 时，有 (f(n) ≤ c g(n))。
• (f(n) = Ω(g(n))) — 下界：表示增长速度不低于 (g(n))。
• (f(n) = Θ(g(n))) — 紧确界：同时满足 (O) 和 (Ω)，即增长速率与 (g(n)) 相同。
• (f(n) = o(g(n))) — 严格上界：(lim_{n→∞} f(n)/g(n) = 0)，说明 (f(n)) 增长远慢于 (g(n))。
• (f(n) = \tilde{O}(g(n))) — 忽略对数因子：等价于 (O(g(n) \log^k n))，其中 (k) 为某常数。

最好、最坏与平均情况分析：

• 最坏情况：针对相同规模的所有可能输入中，算法所需资源的最大值，是最常用的评估标准。
• 最好情况：最小资源消耗的情况。
• 平均情况：基于输入分布计算期望性能。

push_back

二、常见时间复杂度等级（按增长速度升序排列）

• (O(1))：常数时间 — 如数组元素访问、栈顶或队列首尾操作。
• (O(\log n))：对数时间 — 典型如二分查找、平衡二叉搜索树中的查找/插入操作，以及堆结构的插入与删除。
• (O(n))：线性时间 — 适用于顺序遍历、单次哈希表构建、BFS 等。
• (O(n \log n))：线性对数时间 — 归并排序、快速排序（平均）、堆排序及 FFT 算法均属此类。
• (O(n^2))：平方时间 — 常见于冒泡排序、插入排序或双重循环暴力匹配。
• (O(n^3))：立方时间 — 如朴素矩阵乘法实现。
• (O(2^n))：指数时间 — 出现在未优化的子集枚举或某些递归穷举场景。
• (O(n!))：阶乘时间 — 所有排列的完全枚举问题。

push

三、常用数据结构与算法复杂度对照表

以下列出主要数据结构及算法在典型操作下的平均与最坏时间复杂度，以及额外空间开销（注：(n) 表示节点数量，(m) 表示边数；α(n) 为反阿克曼函数，增长极缓，实际中可视为常数）。

数据结构/算法	查找	插入	删除	构造/遍历	空间
数组（支持随机访问）	O(1)	O(n)（中间插入）	O(n)	O(n)	O(1)（额外）
动态数组 / vector（摊销分析）	O(1) 访问	均摊 O(1)（末尾插入），最坏 O(n)（扩容）	O(1) 尾部删除	O(n)	O(n)
单链表	O(n)	O(1)（头部插入）	O(1)（已知前驱节点）	O(n)	O(1)
双向链表	O(n)	O(1)（已知位置）	O(1)	O(n)	O(1)
哈希表（均匀散列，链地址法或开放寻址）	平均 O(1)，最坏 O(n)	平均 O(1)，最坏 O(n)	平均 O(1)	O(n)	O(n)
平衡二叉搜索树（AVL / 红黑树）	O(log n)	O(log n)	O(log n)	O(n)	O(n)
堆（二叉堆）	—	O(log n) 插入	O(log n) 弹出最值	O(n)	O(n)
并查集（路径压缩 + 按秩合并）	α(n)	α(n)	—	O(n)	O(n)
BFS / DFS（邻接表存储）	—	—	—	O(n + m) 时间，O(n) 额外空间	O(n + m) 存图
Dijkstra（使用二叉堆）	—	—	—	O(m log n)	O(n + m)
Dijkstra（使用斐波那契堆优化）	—	—	—	O(n log n + m)	O(n + m)
Kruskal 算法	—	—	—	O(m log m)（排序）+ α(n)	O(n + m)
快速排序	平均 O(n log n)，最坏 O(n)（退化情形）	—	—	平均 O(log n) 递归栈	O(1) 或 O(log n) 额外空间
归并排序	O(n log n)	O(n log n)	—	O(n) 额外空间	O(n) 额外空间

push_back

四、递归式求解方法（常用工具）

对于形如 (T(n) = aT(n/b) + f(n)) 的递推关系，常用以下策略进行分析：

• 主定理（Master Theorem）是处理此类分治递归的标准工具，可根据 (f(n)) 与 (n^{\log_b a}) 的相对大小得出渐近界。
• 递归树法：将递归展开为树状结构，逐层求和估算总代价。
• 代换法：通过猜测解的形式并用数学归纳法验证。
• 伸缩法或其他变换技巧可用于特殊形式的递推。

这些方法帮助我们准确评估递归算法的时间复杂度，尤其在分治、动态规划和树形结构遍历中广泛应用。

find

主定理（Master Theorem）是分析分治算法时间复杂度的重要工具。其适用形式为递推关系式：

T(n) = aT(n/b) + f(n)，其中 a ≥ 1，b > 1。

通过比较函数 f(n) 与 n^log_ba 的增长速率，主定理可将结果分为以下三种情况：

若 f(n) = O(n^{log_ba - ε})，其中 ε > 0，则 T(n) = Θ(n^log_ba)。

若 f(n) = Θ(n^log_ba log^kn)，k ≥ 0，则 T(n) = Θ(n^log_ba log^k+1n)。

若 f(n) = Ω(n^{log_ba + ε})，且满足正则条件 af(n/b) ≤ cf(n)（对某个 c < 1 和足够大的 n 成立），则 T(n) = Θ(f(n))。

push_back

常见应用实例包括：

• 归并排序：T(n) = 2T(n/2) + O(n)，对应第二种情形，得到时间复杂度为 Θ(n log n)。
• 快速排序（平均情况）：同样满足 T(n) = 2T(n/2) + O(n)，因此平均时间复杂度也为 Θ(n log n)。
• Strassen 矩阵乘法：T(n) = 7T(n/2) + O(n)，此时 log7 ≈ 2.807，故复杂度为 O(n^2.807)。

push

除了主定理外，递归树法、主定理的变体以及替代法（即提出猜想并通过数学归纳法证明）也是求解递推式的常用手段。

均摊复杂度（Amortized Complexity）

均摊复杂度关注的是一系列操作的整体性能表现，而非单个操作的最坏情况。对于一个长度为 m 的操作序列，若总时间成本为 O(m·a(n))，则称每次操作的均摊代价为 O(a(n))。这意味着尽管某些操作可能开销较大，但整体上平均每步的代价仍然可控。

常用的均摊分析方法有以下三种：

聚合方法（Aggregate Method）：
计算 m 次操作的总成本 T(m)，然后取平均值 T(m)/m 来得出均摊代价。

记账方法（Accounting Method）：
为每个操作设定一个“摊还费用”，高于实际成本的部分视为存入“信用账户”，用于抵消后续高成本操作的支出。必须确保任意时刻的操作都能被账户中的余额覆盖。

势能方法（Potential Method）：
引入一个势能函数 Φ，它将数据结构的状态映射为一个非负实数。第 i 次操作的摊还成本定义为：c_i + Φ(S_i) - Φ(S_i-1)，其中 c_i 是实际成本，S_i 表示第 i 步后的状态。整个操作序列的总摊还成本等于实际总成本加上末态与初态势能之差 Φ(S_m) - Φ(S₀)。合理构造 Φ 可有效证明复杂度上界。

典型均摊分析案例：动态数组扩容

在实现如动态数组（例如 ArrayList 或 vector）时，当存储空间不足时通常采用“容量翻倍”策略：新建一个大小为原容量两倍的新数组，并将原有元素全部复制过去。

操作代价分析：

• 正常插入操作：O(1)
• 扩容时的复制操作：O(n)，n 为当前元素数量

使用不同方法进行均摊分析：

聚合方法：
考虑从空数组开始执行 n 次插入操作。总共发生的复制次数可以累加估算：最后一次扩容最多复制 n 个元素，前一次最多复制 n/2，再前一次 n/4，依此类推。总复制量不超过 n + n/2 + n/4 + ... < 2n，因此总成本为 O(n)，均摊到每次操作为 O(1)。

记账方法：
为每次插入操作收取 3 单位摊还费用：1 单位用于当前插入操作本身，其余 2 单位作为预存“信用”。每当发生扩容时，这些预先积累的信用可用于支付元素迁移的成本，从而保证整体平衡。

势能方法：
定义势能函数 Φ = 2 × size - capacity，其中 size 是当前元素个数，capacity 是当前容量。该函数反映了系统中“未使用的潜力”。利用此函数可严格推导出每次操作的摊还成本为常数级。

综上所述，动态数组的插入操作具有 O(1) 的均摊时间复杂度。

结论：

均摊复杂度为 O(1)，但单次操作最坏情况为 O(n)。

push_back

2) 带按秩合并与路径压缩的并查集（Union-Find）—— 均摊性能近乎常数

主要操作包括：

find

与

union

。

对于任意 m 个操作，总时间复杂度为 O(mα(n))，其中 α(n) 是反阿克曼函数。该函数增长极其缓慢，在实际应用范围内通常不超过 4。

其证明依赖于复杂的摊还分析方法（如 Tarjan 提出的函数序列法），此处不展开细节。结论是：每次操作的均摊代价接近常数级别。

3) 二叉堆与 Fibonacci 堆的操作复杂度对比

在二叉堆中：

insert

和

extract-min

操作的时间复杂度如下：

• insert

  ：最坏情况下为 O(log n)（元素上浮过程），均摊也为 O(log n)，无摊还优势。

Fibonacci 堆则提供更优的均摊性能：

• insert

  ：均摊 O(1)

• decrease-key

  ：均摊 O(1)

• extract-min

  ：均摊 O(log n)

尽管性能优越，其实现机制较为复杂。

4) Splay Tree（伸展树）—— 所有基本操作均摊 O(log n)

伸展树通过自调整结构实现高效访问。查找、插入、删除等操作的均摊时间复杂度均为 O(log n)。

该结果基于势能函数分析，该函数反映树的整体“不平衡程度”或未来的潜在操作成本。对任意访问序列，单次操作的均摊开销可被控制在对数级别。

七、常见的摊还复杂度证明技巧与分析范式

• 聚合分析 —— 统计每个元素被处理的次数：适用于复制、移动、合并类操作，通过总计所有元素的操作频次推导总体复杂度。
• 构造势能函数：用于平衡树、伸展树及部分堆结构；关键在于选择能体现“未来操作储备”的势能变量。
• 区分均摊与最坏情况：即使给出了均摊复杂度，也需说明单次操作的最坏代价（例如 vector 的 push_back 最坏为 O(n)）。
• 将代价分摊到元素：若能证明每个元素仅会被有限次重新处理或移动，则整体复杂度可达 O(n)。

八、空间复杂度详解：标注方式与常见类型

• O(1)：使用常数额外空间，变量数量不随输入规模 n 增长。
• O(log n)：常见于递归算法中的调用栈深度，或其他对数级辅助存储。
• O(n)：典型如数组、链表、图节点属性存储等线性结构。
• O(n + m)：适用于图的邻接表表示，n 为节点数，m 为边数。
• O(n)：出现在邻接矩阵、稠密距离矩阵或某些动态规划表中。
• 外存与 I/O 复杂度：当数据量过大无法全部载入内存时，需考虑磁盘读写开销。

注意：应区分输入本身占用的空间与算法所需的额外辅助空间（auxiliary space）。通常，“额外空间”不包含输入所占内存。

九、重要算法复杂度的证明要点简析

• 比较排序的下界 Ω(n log n)：利用比较树模型证明。叶子节点数至少为 n!，树的高度至少为 log(n!) = Θ(n log n)，因此任何基于比较的排序算法在最坏情况下至少需要这么多比较。
• 快速排序的平均复杂度：平均比较次数约为 1.386 n log n（具体常数取决于 pivot 选取策略）。最坏情况为 O(n)，可通过随机化 pivot 实现期望 O(n log n) 性能。
• FFT（快速傅里叶变换）：采用分治策略，满足递推式 T(n) = 2T(n/2) + O(n)，解得时间复杂度为 O(n log n)。
• Dijkstra 算法的不同实现复杂度：
  • 使用二叉堆：O((n + m) log n) ≈ O(m log n)
  • 使用斐波那契堆：O(n log n + m)，在稀疏图中优势显著。

十、复杂度分析中的常见误区与工程实践建议

• 忽略常数因子与内存局部性：理论上 O(n) 优于 O(n log n)，但在实际中差距可能不大；缓存命中率和内存访问模式往往更影响性能。
• 平均/期望 vs 最坏情况：哈希表平均查找为 O(1)，但最坏可达 O(n)（严重冲突或遭受攻击）。实时或安全系统必须关注最坏情形。
• 输入分布假设的风险：平均复杂度假设输入服从某种分布，若分布未知或可被恶意操控（如安全场景），仅报告平均情况存在风险。
• 时间与空间的权衡：例如使用哈希表以空间换时间，或构建预计算表（lookup table）提升查询速度。
• 低阶项与实现常数的影响：对于小规模输入 n，常数项和底层实现细节往往比渐近复杂度更重要。
• 算法稳定性与精度问题：某些“更快”的算法可能在数值稳定性或精度方面表现较差（如近似算法）。

十一、进阶话题概览

• 随机化算法：使用期望时间复杂度或概率边界进行分析，例如快速选择算法的期望时间为 O(n)。
• 并行算法复杂度：考虑并行执行下的工作量（work）与跨度（span），评估加速比与效率。

在算法分析中，除了传统的时间复杂度之外，还需考虑多种扩展模型来更精确地刻画性能表现。以下是几个关键的分析维度：

PRAM 模型：该模型关注并行计算中的时间、工作量（work）与深度（span）之间的关系。其中，“工作量”指所有处理器执行的操作总数，“深度”表示最长的依赖路径，即并行执行所需的时间下界。

外存模型（I/O 复杂度）：适用于数据规模超出内存容量的场景，重点在于块访问次数（记为 B），以及可用内存大小（记为 M）。目标是最小化磁盘 I/O 操作，而非单纯的 CPU 运算次数。

分布式系统的通信成本：在网络环境下，时间开销不仅来自计算，还显著受网络往返延迟和消息数量的影响。减少通信轮次和传输量是优化的关键方向。

参数化复杂度与近似算法：面对 NP-hard 问题时，常采用参数化方法（如 FPT 算法）或设计近似算法，在可接受时间内获得接近最优解的结果。

push

十二、动态数组均摊分析示例

考虑一个初始容量为 1 的空动态数组，进行 n 次插入操作：

• 当当前元素数量小于容量时，直接写入新元素，成本为 1；
• 当 size == capacity 时，需将容量翻倍，将原数组的所有元素复制到新空间（此步成本等于原容量），再插入新元素。

扩容过程发生的容量点为：1, 2, 4, 8, ..., 直至不超过 n。

总的复制次数为等比数列求和：
1 + 2 + 4 + ... ≤ n，其和严格小于 2n。

因此，包括插入和复制在内的总写操作次数不超过 3n，均摊到每次插入的成本不超过 3，故均摊时间复杂度为 O(1)。

记账法解释：
每次插入收取 3 单位费用：

• 1 单位用于本次写入操作；
• 2 单位预存，作为未来扩容时移动该元素的“准备金”。

当发生扩容并需复制 k 个元素时，这 k 个元素各自之前已积累 2 单位，足以支付复制成本，系统始终不会透支。

势能法建模：
定义势函数 Φ = 2 × size - capacity（保证非负）。通过该函数可证明每一步的实际成本加上势能变化量恒定，从而得出摊还成本为 O(1)。

十三、常见算法复杂度汇总

• 二分查找：O(logn)
• 基于比较的排序：理论下界 Ω(nlogn)，高效算法可达 O(nlogn)
• 哈希表操作（查找/插入）：均摊 O(1)，最坏情况 O(n)
• 动态数组 push 操作：均摊 O(1)
• 并查集操作（带路径压缩与按秩合并）：均摊 O(α(n))
• BFS 与 DFS 遍历：O(n + m)，其中 n 为顶点数，m 为边数
• Dijkstra 算法（使用二叉堆）：O(mlogn)
• Bellman-Ford 最短路径算法：O(nm)
• Kruskal 算法求最小生成树（MST）：O(mlogm)