时间复杂度与空间复杂度分析方法

复杂度分析是衡量算法效率的核心指标，它忽略硬件、语言等环境差异，聚焦算法本身的 “执行效率”（时间）与 “资源占用”（空间）随数据规模增长的变化规律。以下分两部分详解分析方法。

一、时间复杂度：衡量算法 “执行快慢” 的核心

时间复杂度表示算法执行时间随数据规模（通常用n表示，如数组长度、图的顶点数）增长的趋势，而非具体执行时间（受 CPU 速度、代码细节影响）。分析时需抓住 “关键操作的执行次数” 这一核心。

1. 分析步骤（四步走）

步骤 1：确定 “基本操作”

基本操作是算法中重复执行次数最多、对时间影响最大的操作，通常是循环内的核心语句（如比较、赋值、计算）。

例：快速排序中的 “基准元素与其他元素的比较”、二分查找中的 “中间值与目标值的比较”、动态规划中的 “状态转移计算”。

步骤 2：统计基本操作的 “执行次数”

根据数据规模n，推导出基本操作执行次数的数学表达式（记为T(n)）。

若无循环 / 递归：执行次数是常数（如单个赋值、判断），T(n)=C（C为常数）。
若有循环：需分析循环执行次数（单层循环看循环变量范围，多层循环看嵌套关系）。

例：
线性遍历数组：for (int i=0; i<n; i++) { 基本操作; } → 基本操作执行n次 → T(n)=n。
嵌套循环（矩阵遍历）：for (int i=0; i<n; i++) for (int j=0; j<n; j++) { 基本操作; } → 执行n×n次 → T(n)=n²。

步骤 3：简化表达式（保留 “最高阶项”）

忽略表达式中的常数项、低阶项和最高阶项的系数，因为当n足够大时（如n=10⁶），这些项对增长趋势的影响可忽略。

简化规则：

去掉常数项：T(n)=n+5 → 保留n（5 可忽略）。
去掉低阶项：T(n)=n²+3n → 保留n²（3n 远小于 n²，当 n>3 时）。
去掉最高阶系数：T(n)=2n³ → 保留n³（系数 2 不影响增长趋势）。

步骤 4：用 “大 O 符号” 表示

将简化后的表达式用O(·)包裹，即时间复杂度O(f(n))，其中f(n)是简化后的最高阶项。

例：

T(n)=C → 简化为1 → 时间复杂度O(1)。
T(n)=n+5 → 简化为n → 时间复杂度O(n)。
T(n)=n²+3n+2 → 简化为n² → 时间复杂度O(n²)。

2. 常见时间复杂度类型（按效率从高到低排序）

复杂度	名称	增长趋势	典型场景（结合之前学的算法）
`O(1)`	常数复杂度	不随 n 增长	哈希查找（平均情况）、数组随机访问、原地交换
`O(logn)`	对数复杂度	增长极慢	二分查找（有序数组）、平衡二叉树查找
`O(n)`	线性复杂度	随 n 线性增长	线性查找、BFS/DFS 的遍历（图顶点数为 n 时）
`O(nlogn)`	线性对数复杂度	增长较平缓	快速排序、归并排序、堆排序（平均情况）
`O(n²)`	平方复杂度	随 n² 增长	冒泡排序、插入排序、弗洛伊德算法（n 为顶点数）
`O(2ⁿ)`	指数复杂度	增长极快	未优化的递归斐波那契数列、子集枚举
`O(n!)`	阶乘复杂度	增长最快（极少用）	全排列枚举（数据规模 n≤10）

3. 特殊情况：最坏、最好、平均时间复杂度

部分算法的执行时间受 “数据分布” 影响，需区分三种场景：

最坏时间复杂度：算法在 “最不利输入” 下的时间复杂度（需重点关注，是算法的 “性能上限”）。

例：快速排序（选第一个元素为基准），若输入数组已有序，每次划分仅减少 1 个元素，基本操作执行n+(n-1)+...+1 = n(n+1)/2次 → 最坏时间复杂度O(n²)。
最好时间复杂度：算法在 “最有利输入” 下的时间复杂度（参考意义有限）。

例：快速排序若每次划分都将数组分为两半，基本操作执行nlogn次 → 最好时间复杂度O(nlogn)。
平均时间复杂度：考虑所有可能输入的概率，计算执行时间的期望值（最接近实际运行情况）。

例：快速排序（随机选基准）的平均时间复杂度O(nlogn)，哈希查找的平均时间复杂度O(1)。

二、空间复杂度：衡量算法 “内存占用” 的指标

空间复杂度表示算法所需 “额外空间” 随数据规模n增长的趋势，不包含 “输入数据本身的空间”（如传入的数组、图的邻接表），仅统计算法执行过程中 “临时创建的空间”（如临时变量、递归栈、辅助数组）。

1. 分析步骤（三步走）

步骤 1：确定 “额外空间”

额外空间是算法为了执行而主动创建的、与输入数据无关的空间，主要包括：

临时变量（如循环变量i、中间计算值temp）；
辅助数据结构（如动态规划的dp数组、归并排序的临时合并数组）；
递归栈空间（递归算法中，每一层递归会创建栈帧存储参数、返回地址等）。

步骤 2：分析额外空间的 “增长趋势”

根据数据规模n，判断额外空间的大小是否随n增长：

若额外空间是固定大小（不随n变）：如int i=0;、temp=a+b; → 空间大小为常数。
若额外空间随n增长：如辅助数组int[] dp = new int[n]; → 空间大小为n；递归深度为logn → 栈空间大小为logn。

步骤 3：用 “大 O 符号” 简化表示

与时间复杂度规则一致，忽略常数、低阶项和系数，用O(g(n))表示空间复杂度，g(n)是额外空间的增长趋势。

2. 常见空间复杂度类型及示例（结合经典算法）

复杂度	典型场景（对应之前算法）	额外空间说明
`O(1)`	堆排序、二分查找（迭代实现）、原地交换算法	仅用固定临时变量（如堆调整的`i`、`left`、`right`），无额外数组 / 栈
`O(logn)`	快速排序（递归实现）、二分查找（递归实现）	递归栈深度：快速排序递归划分`logn`层，每层栈帧固定大小 → 总空间`logn`
`O(n)`	归并排序、动态规划（0-1 背包的`dp`数组）、BFS 队列	归并排序需`n`大小的临时合并数组；0-1 背包的`dp`数组大小为`n`（背包容量）
`O(n²)`	弗洛伊德算法（邻接矩阵存储）、动态规划（最长公共子序列的`dp`二维数组）	弗洛伊德算法的距离矩阵大小为`n×n`（`n`为顶点数）；最长公共子序列的`dp`数组为`n×m`（`n`、`m`为字符串长度）

3. 关键注意点：递归的空间复杂度

递归算法的空间复杂度需额外考虑 “递归栈空间”，栈深度等于递归的最大层数：

例 1：递归实现斐波那契数列fib(n) = fib(n-1) + fib(n-2)，递归深度为n → 空间复杂度O(n)（而非O(1)）。
例 2：递归实现二分查找，每次递归将n缩小一半，递归深度为logn → 空间复杂度O(logn)（迭代实现则为O(1)）。

三、复杂度分析实战：结合经典算法举例

通过具体算法验证分析方法，帮你巩固理解：

示例 1：二分查找（迭代实现）

基本操作：中间值与目标值的比较（mid = (left + right)/2; if (nums[mid] == target)）。
执行次数：每次查找将区间缩小一半，最多执行log₂n次（如n=8时，最多查 3 次：8→4→2→1） → T(n)=logn。
时间复杂度：简化为O(logn)。
额外空间：仅用left、right、mid三个临时变量（固定大小） → 空间复杂度O(1)。

示例 2：0-1 背包（动态规划，二维 dp 数组）

基本操作：状态转移计算（dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])）。
执行次数：dp数组为(n+1)×(C+1)（n为物品数，C为背包容量），每个元素计算 1 次 → T(n)=n×C，若C与n同阶（如C=n），则T(n)=n² → 时间复杂度O(n²)。
额外空间：二维dp数组大小为(n+1)×(C+1) → 空间复杂度O(n×C)（若优化为一维dp数组，可降为O(C)）。

示例 3：深度优先搜索（DFS，递归实现）

基本操作：顶点访问与邻接顶点遍历（for (int v : adj[u]) { if (!visited[v]) dfs(v); }）。
执行次数：每个顶点访问 1 次，每条边遍历 1 次（无向图边数m≤n²） → 总次数n+m，若m与n同阶（稀疏图），则T(n)=n → 时间复杂度O(n)。
额外空间：递归栈深度（最坏情况为链状图，深度n） + visited数组（大小n） → 空间复杂度O(n)。

四、复杂度分析的核心原则

关注 “增长趋势” 而非具体数值：比如O(n)和O(n+1000)本质效率相同，因为当n=10⁶时，1000 可忽略。
时间与空间的 “权衡”：多数场景下，优化时间会牺牲空间（如动态规划用dp数组存子问题解，换时间），反之亦然（如原地排序算法用O(1)空间，换时间）。
优先保证 “最坏时间复杂度”：实际开发中，需避免算法在极端情况下出现O(2ⁿ)等低效复杂度（如快速排序需随机选基准，避免最坏情况）。

时间复杂度与空间复杂度分析方法