1 概述与基本概念
复杂度分析是研究计算过程资源消耗的基本方法，主要关注当输入规模增大时，算法、程序或系统在时间、空间以及其他资源上的变化规律。它不强调某一次具体运行的细节，而重视整体增长趋势，因此常被用作评价效率和可扩展性的统一框架。
1.1 复杂度分析的定义
复杂度分析是对计算任务所需资源进行定量估计的过程。这里的“资源”通常指执行时间和存储空间，也可扩展到通信量、随机数使用量、比较次数、调用次数等指标。分析结果一般以输入规模的函数表示，从而揭示资源消耗随问题规模变化的规律。
1.2 研究对象与适用范围
复杂度分析的对象包括算法、数据结构、计算模型中的程序过程，以及更抽象的决策问题和优化问题。它既适用于排序、查找、图遍历等具体算法，也适用于递归过程、在线算法和随机算法等更广泛的计算场景。只要问题可以用明确的输入规模描述，复杂度分析通常就具有适用性。
1.3 复杂度分析的基本目的
复杂度分析的核心目的，是判断某种方法是否高效，以及在规模扩大时是否仍能保持可接受的性能。它可用于比较不同算法的优劣、指导程序优化、预测大规模数据处理能力，并帮助理论研究者建立关于计算难度的抽象分类。
2 渐进表示法
渐进表示法用于描述函数在输入趋于增长时的主导行为，避免被低阶项和常数因子干扰。它是复杂度分析中最常用的语言，能够用简洁形式表达“增长得多快”这一核心问题。
2.1 大 O 记号
大 O 记号用于描述函数的上界，表示某个量不会超过另一函数的某个常数倍在足够大规模下的增长速度。它常被用来表述算法的最坏情况资源消耗上限。
2.1.1 上界的含义
若某算法的时间复杂度为 O(f(n))，通常意味着当输入规模足够大时，其运行时间不会比 f(n) 的某个常数倍增长得更快。这个表达强调的是约束关系，而非精确值，因此常用于保证算法性能不会失控。
2.1.2 常见函数增长阶
常见的增长阶包括常数级、对数级、线性级、线性对数级、平方级、多项式级、指数级和阶乘级等。它们按增长快慢大致排列，前者通常表示较高效率，后者则意味着规模扩大后资源需求急剧上升。
2.2 Ω 记号
Ω 记号用于描述函数的下界，表示某个量至少以另一函数的某个常数倍增长。它常用于说明问题或算法在某些条件下不可避免的最低代价。
2.2.1 下界的含义
如果一个过程具有 Ω(f(n)) 的复杂度，说明无论采用何种实现方式，在足够大的输入规模下，其资源消耗至少达到某种增长水平。下界分析常用于证明算法的理论极限，也可用于说明某类问题存在不可避免的计算成本。
2.3 Θ 记号
Θ 记号表示紧确界，即一个函数既是另一个函数的上界，也是其下界。它常用来刻画算法资源消耗的准确渐进阶。
2.3.1 紧确界与等价关系
当某算法的复杂度为 Θ(f(n)) 时，意味着它的增长速度与 f(n) 在渐进意义上同阶。这个结论比单纯的大 O 或 Ω 更强，因为它同时给出了上下界，从而形成更精确的刻画。
2.4 o 记号与ω 记号
o 记号和 ω 记号用于描述严格的渐近关系。前者表示增长显著慢于某函数，后者表示增长显著快于某函数，二者常用于更细致的比较。
2.4.1 严格渐近比较
若 f(n) 属于 o(g(n))，通常表示 f(n)/g(n) 在极限意义下趋于 0；若属于 ω(g(n))，则表示比 g(n) 增长更快，且比值趋于无穷大。这类记号在证明复杂度严格优劣时十分有用。
3 时间复杂度
时间复杂度衡量算法完成任务所需的计算步数或运行时间随输入规模变化的规律。它是最常见的复杂度指标之一，也是评估算法效率的基础。
3.1 基本定义
时间复杂度通常以基本操作次数作为度量，例如比较、赋值、加减、访问数组元素等。分析时会将这些操作的数量表示为输入规模的函数，并再用渐进记号概括其主要增长趋势。
3.2 最坏情况复杂度
最坏情况复杂度描述算法在所有可能输入中所耗费资源的最大值。它具有较强的安全性，适合用于性能保障和上限估计，因此在理论分析和工程设计中都很常见。
3.3 最好情况复杂度
最好情况复杂度描述算法在最有利输入下的最低资源消耗。它能反映算法在理想条件下的表现，但单独使用时往往不足以说明实际性能，因为真实输入未必总是最理想的。
3.4 平均情况复杂度
平均情况复杂度关注算法在典型输入上的期望表现，通常比最好情况更接近实际体验。它需要建立关于输入出现概率的假设，因此分析结果往往依赖模型设定。
3.4.1 概率模型与输入分布
平均情况分析通常假设输入来自某一概率分布，或者默认所有输入等可能出现。在不同分布下，同一算法的平均复杂度可能明显不同，因此概率模型的选择会直接影响结论。
3.5 均摊复杂度
均摊复杂度研究一系列操作的平均代价，而不是单次操作的瞬时开销。它适用于某些单次代价波动较大、但长期平均成本稳定的算法和数据结构。
3.5.1 记账法
记账法通过给某些便宜操作多分配一点“信用”，用来补贴未来可能较贵的操作。这样可以把复杂操作的成本分散到多个步骤上，从而证明整体平均代价较低。
3.5.2 势能法
势能法借助一个反映系统状态的势函数，将当前的额外代价转化为未来的可抵扣资源。它特别适合分析动态数据结构和操作序列，因为能够更自然地表达状态变化带来的成本转移。
4 空间复杂度
空间复杂度衡量算法在执行过程中需要占用的存储资源。与时间复杂度不同，空间复杂度关注的是内存使用规模，包括临时变量、辅助结构以及递归调用带来的额外开销。
4.1 额外空间与总空间
额外空间指除输入本身之外所使用的附加存储；总空间则包括输入数据所占空间和辅助空间。工程与理论中常常优先关注额外空间，因为它更能反映算法运行时的新增负担。
4.2 递归栈空间
递归算法在执行时会为每一层调用保存局部信息，因此会产生栈空间开销。递归深度越大，栈占用通常越高，这也是分析递归算法时不可忽视的一部分。
4.3 原地算法与空间优化
原地算法指在有限额外空间内完成计算，通常只使用常数级辅助存储。空间优化则是通过复用数组、压缩状态或减少中间结构等方式，降低内存占用，但有时会以增加时间开销为代价。
5 复杂度分析的方法
复杂度分析既有通用思路，也有针对不同结构的专门技巧。选择合适的方法，往往取决于代码形态、递归关系以及需要证明的复杂度类型。
5.1 循环分析
循环分析是最直接的复杂度求法，常通过估计循环次数和每次迭代的代价来完成。对于结构清晰的程序，这种方法通常简洁明了。
5.1.1 单层循环
单层循环的复杂度通常由循环执行次数决定。如果每次迭代执行固定数量的基本操作，则总复杂度与循环次数成正比。
5.1.2 嵌套循环
嵌套循环的复杂度一般等于各层迭代次数的乘积或组合结果。若内层循环次数随外层变量变化，则需要分别求和，不能简单地按最外层次数粗略估计。
5.2 递归关系分析
递归关系分析用于处理自调用算法，通过建立递推式来描述问题规模缩小后的总代价。它在分治算法、树形过程和动态规划中尤为常见。
5.2.1 代入法
代入法先猜测复杂度形式，再通过数学归纳法验证其正确性。它适合处理已有经验判断或易于猜测上界的递归式。
5.2.2 递归树法
递归树法将递推式展开成树形结构，观察每一层的总代价并求和。它直观地揭示了递归各层的贡献，便于理解问题规模如何在层层分解中累积成本。
5.2.3 主定理
主定理是分析形如 T(n)=aT(n/b)+f(n) 的递归式的重要工具。它通过比较子问题总量与合并代价的相对大小，快速给出常见分治递归的渐进结果。
5.3 摊还分析
摊还分析用于评估操作序列的平均成本，尤其适合处理偶发性高成本操作。与单次最坏情况不同，它关注长期整体表现，因此更能体现数据结构的真实效率。
5.4 实验与理论结合的分析
在某些复杂系统中，纯理论分析难以覆盖全部细节，因此会结合实验测量、性能剖析和统计建模。理论分析负责给出趋势和边界，实验则帮助验证假设并发现常数因素和实现层面的影响。
6 计算模型
复杂度分析必须依赖某种计算模型，因为不同模型对“操作”的定义并不相同。模型选择会影响复杂度表达的方式，也会影响结论的适用范围。
6.1 RAM 模型
RAM 模型将计算机抽象为随机访问存储器，假设基本指令可以在常数时间内执行。它是算法分析中最常见的理想化模型，尤其适合讨论一般程序和数组操作。
6.2 位复杂度模型
位复杂度模型把数据看作由二进制位组成，关注实际位运算和数据长度对成本的影响。它更适合研究大整数运算、密码学算法和低层实现细节，因为某些在 RAM 模型下算作常数的操作，在位级别上并不恒定。
6.3 图灵机模型
图灵机模型是理论计算机科学中的经典抽象模型，用于刻画可计算性与复杂性。它虽然不直接对应现实硬件，但在证明复杂度下界和研究问题本质难度方面具有重要地位。
6.4 随机访问与真实硬件差异
现实计算机具有缓存、分支预测、并行执行和内存层次结构等特征，这些因素会让实际运行时间与理想模型产生差别。因此，复杂度分析提供的是渐进趋势，而不是对具体硬件性能的直接预测。
7 常见复杂度类别
复杂度类别用于按增长速度对算法进行分类，帮助快速判断其可扩展性。不同类别之间通常存在明显的性能差异，尤其在输入规模较大时更为显著。
7.1 常数时间
常数时间表示操作开销不随输入规模变化。此类过程通常只涉及固定次数的基本操作，常见于简单赋值、固定索引访问或某些已知范围内的判断。
7.2 对数时间
对数时间意味着输入规模每次都按比例缩小，所需步骤与对数函数增长一致。二分查找是这一类别的典型例子，体现了“每次减少一半”的高效策略。
7.3 线性时间
线性时间表示复杂度与输入规模成正比。许多基础算法，如顺序扫描、单次遍历和简单聚合操作，都属于这一类，通常被视为较实用的高效方案。
7.4 线性对数时间
线性对数时间介于线性与平方之间，常见于某些分治与排序算法。它的增长速度快于线性，但仍显著优于二次级别，因此在中大规模数据处理中通常具有良好表现。
7.5 平方时间与多项式时间
平方时间常出现在双重循环和部分动态规划算法中。更一般地，多项式时间泛指 n 的某个固定次数幂的增长，通常被视为可接受的计算复杂度范围之一。
7.6 指数时间
指数时间的增长非常迅速，输入规模稍有增加，资源需求就可能大幅上升。它常见于穷举搜索、组合爆炸问题和某些约束求解场景，往往难以用于大规模实例。
7.7 阶乘时间
阶乘时间比指数时间增长更快，通常出现在对所有排列逐一枚举的算法中。此类复杂度通常只适用于极小规模问题，实际应用中很少作为可行方案。
8 复杂度分析中的数学工具
复杂度分析高度依赖数学表达与推导工具。借助这些工具，可以更准确地比较函数增长、求解递推关系并计算平均代价。
8.1 极限与增长率比较
极限用于判断两个函数在无限增长时的相对大小，是证明渐进关系的重要手段。通过比较比值的极限，可判断一个函数是否最终主导另一个函数。
8.2 递推与数列
许多算法的代价可以写成递推式或数列形式。研究这些关系的通项或上界，是分析分治算法、递归程序和动态过程的关键步骤。
8.3 求和公式
求和公式常用于处理循环累积代价和递归树各层成本。对等差、等比以及更一般的级数进行求和，可以将看似复杂的代价表达化简为可分析的形式。
8.4 概率与期望
概率与期望工具主要用于平均情况分析、随机算法和随机化数据结构。通过计算期望代价，可以得到在随机输入或随机选择机制下的典型性能。
9 典型应用
复杂度分析广泛应用于算法设计、程序优化和系统评估，是计算机科学中最常见的分析手段之一。许多经典问题的性能比较，都离不开这一方法。
9.1 排序算法分析
排序算法分析通常比较比较次数、交换次数和额外空间使用。不同排序方法在平均、最坏和空间特性上差异明显，因此复杂度分析是选择排序策略的重要依据。
9.2 查找与检索算法分析
查找问题常涉及顺序检索、二分查找和哈希检索等方法。复杂度分析能够说明不同结构在查找速度、空间占用和冲突处理方面的取舍。
9.3 图算法分析
图算法的复杂度常与顶点数、边数及图的表示方式有关。遍历、最短路、连通性和匹配等问题中，分析结果往往直接决定算法是否适合大规模图数据。
9.4 字符串算法分析
字符串算法关注模式匹配、前缀处理和文本搜索等任务。由于文本长度可能很大，复杂度分析在该领域尤为重要，尤其是对线性扫描和高效匹配方法的评估。
9.5 动态规划分析
动态规划常通过状态数和状态转移成本来估计复杂度。其分析重点通常是状态空间大小、转移次数以及是否存在可进一步优化的重复计算。
10 复杂度分析的局限与误区
复杂度分析虽然强大，但并不能替代所有层面的性能判断。对其适用边界和常见误区保持清醒认识，有助于避免错误结论。
10.1 只看渐进复杂度的局限
渐进复杂度忽略常数因子和低阶项，因此在中小规模数据上未必最能反映真实速度。某些理论上复杂度更高的方法，可能因实现简单而在实际中更快。
10.2 常数因子与工程实践
常数因子、缓存命中率、内存访问模式和编译器优化都会影响实际运行效果。工程实践中，复杂度较优的算法不一定总是最合适的实现。
10.3 输入规模定义不一致
不同问题中的“规模”可能对应长度、节点数、位数、维度或参数总量。若规模定义不统一，复杂度结论之间就难以直接比较，甚至会造成误解。
10.4 平均情况与最坏情况混淆
平均情况复杂度不等于最坏情况复杂度，二者适用前提不同。将两者混为一谈，可能导致对算法稳定性和风险水平的错误判断。
11 相关分支
复杂度分析与多个理论方向密切相关，这些分支从不同角度研究计算难度、资源限制和问题本质。它们共同构成复杂性研究的重要体系。
11.1 计算复杂性理论
计算复杂性理论研究问题本身的难易程度，以及在不同资源限制下哪些问题能够被有效求解。它关注类的划分、归约关系和难题结构，是复杂度分析的理论延伸。
11.2 参数化复杂度
参数化复杂度将问题规模拆分为整体输入与若干关键参数，研究当参数较小时是否能获得更高效的算法。它适用于结构化问题和组合优化任务。
11.3 通信复杂度
通信复杂度研究分布式参与者为完成共同任务而需要交换的信息量。它不仅用于网络与协议分析，也常被用来证明某些算法问题的下界。
11.4 描述复杂度
描述复杂度关注对象的最短描述长度或编码成本。它在数据压缩、信息论和某些形式化推理中具有重要意义，也与算法资源分析存在交叉。
11.5 随机化复杂度
随机化复杂度研究在允许使用随机性的情况下，算法所需的资源边界。随机性有时可以显著提高效率或简化设计，因此这一分支是现代算法理论的重要组成部分。