算法复杂度（Algorithm Complexity）是衡量算法效率的核心指标，分为时间复杂度（Time Complexity）和空间复杂度（Space Complexity）两个维度。时间复杂度描述算法执行所需时间随输入规模增长的变化趋势，空间复杂度描述算法执行所需存储空间随输入规模增长的变化趋势。
为什么需要研究算法复杂度？在现代计算机系统中，数据规模动辄达到百万、亿级，一个低效的算法可能在实际场景中根本无法完成计算。例如，在包含十万个元素的有序数组中查找一个值，使用二分查找（O(log n)）仅需约17次比较，而使用线性查找（O(n)）在最坏情况下需要十万次比较。当数据规模进一步扩大到十亿时，二分查找仅需30次比较，而线性查找需要十亿次——这在实际系统中是不可接受的。
算法复杂度分析的核心思想是忽略常数因子和低阶项，聚焦于算法效率随输入规模增长的主导增长趋势。这种分析方法由Donald Knuth在其经典著作《计算机程序设计艺术》中系统化，是计算机科学领域最基础且最重要的分析工具之一。
大O表示法（Big O Notation）是描述算法渐进复杂度最常用的数学符号体系。它由德国数学家Paul Bachmann于1894年引入，后被计算机科学界广泛采用。大O表示法并非一个单一的符号，而是一组紧密相关的符号系统，包括大O符号、大Omega符号、大Theta符号，分别用于描述函数增长的上界、下界和紧界。
大O符号 O(g(n)) 表示算法的渐进上界，即算法时间不会超过这个级别的增长。定义：存在正常数 c 和 n₀，使得对于所有 n ≥ n₀，有 0 ≤ f(n) ≤ c·g(n)。在实际面试和工程中，最常使用的是大O符号，它给出了算法的最坏情况保证。
大Omega符号 Ω(g(n)) 表示算法的渐进下界，即算法时间至少会达到这个级别的增长。定义：存在正常数 c 和 n₀，使得对于所有 n ≥ n₀，有 0 ≤ c·g(n) ≤ f(n)。大Omega符号常用于描述算法的最佳情况或性能下限。
大Theta符号 Θ(g(n)) 表示算法同时具有上界和下界，即算法的增长恰好是这个级别的。定义：存在正常数 c₁、c₂ 和 n₀，使得对于所有 n ≥ n₀，有 0 ≤ c₁·g(n) ≤ f(n) ≤ c₂·g(n)。当说一个算法的时间复杂度是 Θ(n²) 时，既意味着它不会比 n² 增长更快，也不会比 n² 增长更慢。
小o符号 o(g(n)) 表示非紧的上界，即 f(n) 的增长严格低于 g(n)。类似地，小omega符号 ω(g(n)) 表示非紧的下界。它们在实际工程中使用较少，更多出现在理论分析中。
| 符号 | 名称 | 含义 | 类比 |
|---|---|---|---|
| O(g(n)) | 大O | 渐进上界 | 最坏情况，不超过 |
| Ω(g(n)) | 大Omega | 渐进下界 | 最好情况，至少 |
| Θ(g(n)) | 大Theta | 渐进紧界 | 精确界，恰好 |
| o(g(n)) | 小o | 非紧上界 | 严格小于 |
| ω(g(n)) | 小omega | 非紧下界 | 严格大于 |
算法的时间复杂度可以根据其增长特性划分为若干典型级别。从低到高依次为：常数级、对数级、线性级、线性对数级、平方级、指数级和阶乘级。下面通过代码示例逐一说明。
常数阶表示算法的执行时间不随输入规模变化。无论输入多大，执行时间都是固定的。数组按索引访问、哈希表查找、栈的入栈出栈操作等都是典型的常数阶操作。
// 常数阶 O(1) — 数组随机访问 int getElement(int[] arr, int index) { return arr[index]; // 一次内存寻址，时间恒定 } // 常数阶 O(1) — 交换两个变量 void swap(int& a, int& b) { int temp = a; a = b; b = temp; } // 常数阶 O(1) — 哈希表查找 boolean containsKey(Map<String, Object> map, String key) { return map.containsKey(key); // 理想情况下O(1) }
对数阶表示算法的执行时间随输入规模对数增长。每轮操作将问题规模减半，是分治思想的典型体现。二分查找、平衡二叉搜索树的查找操作等都是对数阶。对数阶非常高效，即使输入规模达到十亿级别，也只需要约30次操作。
// 对数阶 O(log n) — 二分查找 int binarySearch(int[] arr, int target) { int left = 0, right = arr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { left = mid + 1; // 排除左半部分 } else { right = mid - 1; // 排除右半部分 } } return -1; } // 对数阶 O(log n) — 计算2的幂 int powerOfTwo(int n) { int result = 1; while (n-- > 0) { result *= 2; } return result; }
线性阶表示算法的执行时间与输入规模成正比。最简单的线性阶算法是遍历一个长度为 n 的数组并处理每个元素。在大多数实际场景中，线性阶已经是可以接受的时间复杂度。
// 线性阶 O(n) — 查找最大值 int findMax(int[] arr) { int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } return max; } // 线性阶 O(n) — 计算数组元素之和 int sumArray(int[] arr) { int sum = 0; for (int num : arr) { sum += num; } return sum; }
线性对数阶是许多高效排序算法（如归并排序、堆排序、快速排序平均情况）的时间复杂度。它将问题分解为 log n 层，每层执行 O(n) 的操作，合计 O(n log n)。这是目前已知的比较排序算法的理论最优时间复杂度。
// 线性对数阶 O(n log n) — 归并排序 void mergeSort(int[] arr, int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; mergeSort(arr, left, mid); // 递归排序左半 mergeSort(arr, mid + 1, right); // 递归排序右半 merge(arr, left, mid, right); // O(n)合并两个有序数组 } // 合并操作 — O(n) void merge(int[] arr, int left, int mid, int right) { int[] temp = new int[right - left + 1]; int i = left, j = mid + 1, k = 0; while (i <= mid && j <= right) { temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++]; } while (i <= mid) temp[k++] = arr[i++]; while (j <= right) temp[k++] = arr[j++]; System.arraycopy(temp, 0, arr, left, temp.length); }
平方阶表示算法的执行时间与输入规模的平方成正比。通常出现在嵌套循环中。虽然平方阶算法在处理小规模数据时仍然可用，但当 n 增大到一万以上时，平方阶算法将变得非常缓慢。
// 平方阶 O(n²) — 冒泡排序 void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } // 平方阶 O(n²) — 所有数对之和 int sumAllPairs(int[] arr) { int sum = 0, n = arr.length; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { sum += arr[i] + arr[j]; } } return sum; }
指数阶意味着每增加一个输入元素，执行时间翻倍。阶乘阶的增长速度比指数阶更快。这两种复杂度通常出现在暴力搜索、组合优化等场景中。在实际工程中，指数阶和阶乘阶算法仅能处理非常小的输入规模（n ≤ 20-30）。
// 指数阶 O(2ⁿ) — 斐波那契数列（朴素递归） int fibonacci(int n) { if (n <= 1) return n; return fibonacci(n - 1) + fibonacci(n - 2); // 递归树呈指数扩展，存在大量重复计算 } // 阶乘阶 O(n!) — 全排列生成 void permute(int[] arr, int start) { if (start == arr.length - 1) { System.out.println(Arrays.toString(arr)); return; } for (int i = start; i < arr.length; i++) { swap(arr, start, i); permute(arr, start + 1); swap(arr, start, i); // 回溯 } }
| 复杂度 | 名称 | n=10 | n=100 | n=1000 | n=10⁶ | 可处理规模 |
|---|---|---|---|---|---|---|
| O(1) | 常数阶 | 1 | 1 | 1 | 1 | 任意 |
| O(log n) | 对数阶 | ~3 | ~7 | ~10 | ~20 | 极大 |
| O(n) | 线性阶 | 10 | 100 | 1000 | 10⁶ | 大 |
| O(n log n) | 线性对数阶 | ~33 | ~664 | ~9966 | ~2×10⁷ | 较大 |
| O(n²) | 平方阶 | 100 | 10000 | 10⁶ | 10¹² | 小（≤ 10⁴） |
| O(2ⁿ) | 指数阶 | 1024 | 1.3×10³⁰ | 不可计算 | 不可计算 | 极小（≤ 30） |
| O(n!) | 阶乘阶 | 3.6×10⁶ | 不可计算 | 不可计算 | 不可计算 | 极小（≤ 12） |
递归算法的时间复杂度分析比分治算法更复杂，因为递归调用自身会产生递归树，需要借助专门的数学工具。常用的分析方法有三种：代入法、递归树法和主定理。
代入法先猜测递归式的时间复杂度，再用数学归纳法验证。关键在于做出合理的猜测，这需要对常见递归模式有经验积累。
// 以归并排序的递归式 T(n) = 2T(n/2) + O(n) 为例 // 步骤1：猜测 T(n) = O(n log n) // 步骤2：假设 T(k) ≤ c·k·log(k) 对所有 k < n 成立 // 步骤3：代入验证： // T(n) = 2T(n/2) + n // ≤ 2[c·(n/2)·log(n/2)] + n // = c·n·log(n/2) + n // = c·n·log(n) - c·n·log(2) + n // = c·n·log(n) - (c - 1)n // ≤ c·n·log(n) 当 c ≥ 1 时成立 // 结论：T(n) = O(n log n) ✓
递归树法将递归调用展开成树形结构，树的每个节点代表一次递归调用，节点上的值表示该次调用所做的非递归工作量。通过计算所有节点值的总和得到总的时间复杂度。
// 以 T(n) = 3T(n/4) + cn² 为例构建递归树 // // 第0层（根节点）： cn² → cn² // / | \ // 第1层： c(n/4)² c(n/4)² c(n/4)² → 3·c·(n/4)² // / | \ / | \ / | \ // 第2层： ...每节点再分裂为3个... → 9·c·(n/16)² // // 第i层的总代价： 3ⁱ · c · (n/4ⁱ)² = c·(3/16)ⁱ·n² // 树高：log₄(n)，叶子节点数：3^(log₄(n)) = n^(log₄3) // 总代价 = n²·Σ(c·(3/16)ⁱ) + Θ(n^(log₄3)) // 由于 3/16 < 1，级数收敛，主导项为 cn² // 结论：T(n) = O(n²) ✓
主定理是分析分治递归算法最强大的工具。对于形如 T(n) = a·T(n/b) + f(n) 的递归式（其中 a ≥ 1，b > 1），主定理给出了三种情况的结论：
// 主定理应用示例 // // 示例1：T(n) = 9T(n/3) + n // a=9, b=3, f(n)=n // n^(log₃9) = n²，f(n) = n = O(n²⁻¹) // 情况1 → T(n) = Θ(n²) // // 示例2：T(n) = 2T(n/2) + n // a=2, b=2, f(n)=n // n^(log₂2) = n¹ = n，f(n) = n = Θ(n¹·log⁰n) // 情况2 → T(n) = Θ(n·log n) // // 示例3：T(n) = 2T(n/2) + n² // a=2, b=2, f(n)=n² // n^(log₂2) = n，f(n)=n² = Ω(n¹⁺¹) // 情况3 → T(n) = Θ(n²) // // 示例4：T(n) = T(2n/3) + T(n/3) + n // 非标准形式（两项不同），需用递归树法 // 树高约 log₃/₂(n)，各层总计 O(n) → T(n)=Θ(n·log n)
空间复杂度衡量算法执行过程中所需的额外存储空间。与时间复杂度同样重要，在内存受限的环境（如嵌入式系统、移动设备）中尤为关键。
原地算法是指算法仅使用 O(1) 的额外空间来修改输入数据。冒泡排序、选择排序、插入排序、堆排序等都是原地排序算法。原地算法的空间效率最高，但不一定是最优选择，因为它们可能会修改原始数据。
// 原地算法 O(1) — 数组反转 void reverse(int[] arr) { int i = 0, j = arr.length - 1; while (i < j) { int temp = arr[i]; // 仅需O(1)额外空间 arr[i] = arr[j]; arr[j] = temp; i++; j--; } } // 原地算法 O(1) — 移除有序数组中重复元素 int removeDuplicates(int[] nums) { if (nums.length == 0) return 0; int writePos = 1; // 写入位置指针 for (int readPos = 1; readPos < nums.length; readPos++) { if (nums[readPos] != nums[writePos - 1]) { nums[writePos++] = nums[readPos]; } } return writePos; // 新长度 }
许多算法需要分配与输入规模成比例的额外空间。归并排序需要 O(n) 的临时数组合并两个有序子数组；计数排序、桶排序等非比较排序也需要 O(n) 或更多的辅助空间。
// O(n) 额外空间 — 归并排序中的临时数组 void merge(int[] arr, int left, int mid, int right) { int[] temp = new int[right - left + 1]; // O(n)额外空间 // ... 合并逻辑 } // O(n) 额外空间 — 斐波那契数列（自底向上DP） int fibonacciDP(int n) { if (n <= 1) return n; int[] dp = new int[n + 1]; // O(n)数组 dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }
递归算法在调用过程中会消耗系统调用栈空间。每次递归调用都会在栈上分配一个栈帧，包含局部变量、参数和返回地址。递归深度决定了栈空间的使用量。深度为 n 的递归调用需要 O(n) 栈空间，深度为 log n 的递归调用需要 O(log n) 栈空间。
// O(n)栈空间 — 朴素递归 int factorial(int n) { if (n <= 1) return 1; // 递归深度n，栈空间O(n) return n * factorial(n - 1); } // O(log n)栈空间 — 二分查找（递归版） int binarySearchRec(int[] arr, int left, int right, int target) { if (left > right) return -1; int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (arr[mid] > target) return binarySearchRec(arr, left, mid - 1, target); // 深度log₂n return binarySearchRec(arr, mid + 1, right, target); } // 优化：用迭代代替递归消除栈空间 // 斐波那契 O(1)空间（仅需两个变量） int fibonacciOptimized(int n) { if (n <= 1) return n; int prev2 = 0, prev1 = 1, curr = 0; for (int i = 2; i <= n; i++) { curr = prev1 + prev2; // 仅用三个变量 prev2 = prev1; prev1 = curr; } return curr; }
| 空间复杂度 | 说明 | 典型算法 |
|---|---|---|
| O(1) | 原地算法，仅使用固定额外空间 | 冒泡排序、选择排序、插入排序、堆排序、数组反转 |
| O(log n) | 递归深度为对数级别 | 二分查找（递归版）、快速排序（递归栈） |
| O(n) | 需要与输入规模成比例的额外空间 | 归并排序、计数排序、桶排序、动态规划表 |
| O(n²) | 二维矩阵或复杂数据结构 | Floyd-Warshall、图的邻接矩阵、最长公共子序列DP表 |
均摊分析（Amortized Analysis）用于分析那些有"偶发的高成本操作"的算法序列。它不单独分析某次操作的最坏情况，而是分析一系列操作的总时间复杂度，然后取平均值。均摊分析揭示了一个重要事实：某些看似昂贵的操作，在序列上下文中可能被均摊为低成本。
聚合分析计算 n 次操作的总时间复杂度 T(n)，然后均摊到每次操作得到 T(n)/n。这种方法最简单直接，适用于操作类型相同或相近的场景。
// 动态数组（ArrayList）的自动扩容 — 聚合分析 // // 假设初始容量为1，每次容量满时加倍 // 第1次插入：容量1 → 容量已满，扩至2，复制1个元素，插入第2个 // 第2次插入：容量2 → 容量已满，扩至4，复制2个元素，插入第3个 // 第3~4次插入：容量4 → 满时扩至8，复制4个元素 // ... // // n次插入的总复制次数：1 + 2 + 4 + 8 + ... + n/2 = n - 1 // n次插入的总时间复杂度：O(n) // 每次插入的均摊时间复杂度：O(1) // // 这意味着虽然单次扩容操作的成本是O(n)， // 但从序列角度分析，每次插入的均摊成本仅为O(1)
核算法为不同类型的操作分配不同的"摊销成本"。如果实际成本低于摊销成本，差额作为"信用"存入"银行"；当实际成本高于摊销成本时，使用之前积累的信用来支付超额部分。关键在于为每个操作分配合适的摊销成本，使得"银行余额"永远不为负。
// 核算法分析 — 动态数组扩容 // // 为每次插入操作分配3单位的摊销成本： // - 1单位支付当前插入的实际成本 // - 1单位作为"信用"存起来，用于将来该元素被复制时的成本 // - 1单位用于支付该元素在更远将来再次被复制时的成本 // // 扩容时，需要复制现有所有元素，每个元素的复制 // 成本由之前存入的信用支付，不需要额外开销。 // // 关键保证：每次插入的摊销成本O(1)，最坏情况O(n) // 均摊后每次操作的平均成本为O(1)
势能法是最形式化的均摊分析方法。它定义一个势能函数 Φ(Dᵢ) 来表示数据结构在状态 i 下的"势能"。每次操作的均摊成本 = 实际成本 + 势能变化（ΔΦ = Φ(Dᵢ) - Φ(Dᵢ₋₁)）。关键是要设计一个合适的势能函数，使得 Φ(D₀) = 0 且 Φ(Dᵢ) ≥ 0 对所有 i 成立。
// 势能法分析 — 动态数组扩容 // // 定义势能函数：Φ = 2 × size - capacity // 其中 size 是当前元素个数，capacity 是数组容量 // // 情况1：未触发扩容（size < capacity） // 实际成本 = 2（插入操作+赋值） // 势能变化 = [2×(size+1) - cap] - [2×size - cap] = 2 // 均摊成本 = 2 + 2 = 4 = O(1) // // 情况2：触发扩容（size == capacity） // 实际成本 = 1 + size（插入 + 复制size个元素到新数组） // 扩容前势能 = 2×cap - cap = cap // 扩容后势能 = 2×(cap+1) - 2×cap = 2（容量翻倍） // 势能变化 = 2 - cap // 均摊成本 = (1 + size) + (2 - cap) = 1 + cap + 2 - cap = 3 = O(1) // // 结论：动态数组插入操作的均摊时间复杂度为O(1)
同一算法在不同输入下的表现可能差异巨大。为了全面评估算法的性能，通常从三个角度分析：最好情况（Best Case）、最坏情况（Worst Case）和平均情况（Average Case）。
// 快速排序 — 三种情况分析 private int partition(int[] arr, int low, int high) { int pivot = arr[high]; // 选择最后一个元素为pivot int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; swap(arr, i, j); } } swap(arr, i + 1, high); return i + 1; } public void quickSort(int[] arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); // 递归排序左半 quickSort(arr, pi + 1, high); // 递归排序右半 } } // 最好情况 O(n log n)：每次pivot都恰好将数组均分 // 递归式：T(n) = 2T(n/2) + O(n) → T(n) = Θ(n log n) // // 最坏情况 O(n²)：数组已有序且每次选择的都是最小/最大元素 // 递归式：T(n) = T(n-1) + O(n) → T(n) = Θ(n²) // // 平均情况 O(n log n)（假设输入均匀随机） // 递归式：T(n) = T(k) + T(n-1-k) + O(n)，k的期望为n/2 // 期望求解 → T(n) = Θ(n log n)
为了避免最坏情况的发生，实践中常采用随机化技术：随机选择pivot（随机化快速排序）、随机打乱输入、或使用随机化的数据结构（如跳表、随机化二叉搜索树）。随机化算法可将最坏情况的概率降低到可忽略的程度。
// 随机化快速排序 — 避免最坏情况 private int randomizedPartition(int[] arr, int low, int high) { int randomIndex = low + (int)(Math.random() * (high - low + 1)); swap(arr, randomIndex, high); // 随机选择pivot并交换到末尾 return partition(arr, low, high); // 调用标准partition } // 通过随机化，最坏情况发生的概率呈指数级下降 // 算法的时间复杂度的期望值稳定在 O(n log n)
| 算法 | 最好情况 | 平均情况 | 最坏情况 | 说明 |
|---|---|---|---|---|
| 快速排序 | O(n log n) | O(n log n) | O(n²) | 随机化可避免最坏情况 |
| 插入排序 | O(n) | O(n²) | O(n²) | 数据基本有序时高效 |
| 哈希表查找 | O(1) | O(1) | O(n) | 依赖哈希函数质量 |
| 二分查找 | O(1) | O(log n) | O(log n) | 始终对数级 |
| 线性查找 | O(1) | O(n) | O(n) | 目标在首位即最好 |
下面是一份常用数据结构和算法的时间复杂度快速参考表，在算法面试和系统设计中非常实用。
| 数据结构 | 查找 | 插入 | 删除 | 查找最值 | 说明 |
|---|---|---|---|---|---|
| 数组（无序） | O(n) | O(1) | O(n) | O(n) | 按索引访问O(1) |
| 有序数组 | O(log n) | O(n) | O(n) | O(1) | 二分查找，插入需移动 |
| 链表（单向） | O(n) | O(1) | O(n) | O(n) | 已知位置插入O(1) |
| 栈 | — | O(1) | O(1) | — | 后进先出（LIFO） |
| 队列 | — | O(1) | O(1) | — | 先进先出（FIFO） |
| 哈希表 | O(1)* | O(1)* | O(1)* | O(n) | *均摊，最坏O(n) |
| 二叉搜索树（BST） | O(log n)* | O(log n)* | O(log n)* | O(log n) | *平均；最坏O(n) |
| AVL树/红黑树 | O(log n) | O(log n) | O(log n) | O(log n) | 自平衡BST |
| B树/B+树 | O(log n) | O(log n) | O(log n) | O(log n) | 数据库索引常用 |
| 堆（二叉堆） | — | O(log n) | O(log n) | O(1) | 查找最值O(1) |
| Trie（前缀树） | O(k) | O(k) | O(k) | — | k为键长度 |
| 并查集（Union-Find） | — | O(α(n)) | — | — | α(n)为阿克曼反函数 |
| 图（邻接表） | — | O(1) | O(deg(v)) | — | deg(v)为顶点度数 |
| 算法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 冒泡排序 | O(n²) | O(1) | 原地排序，稳定 |
| 选择排序 | O(n²) | O(1) | 原地排序，不稳定 |
| 插入排序 | O(n²) | O(1) | 原地排序，稳定，近似有序时近乎O(n) |
| 希尔排序 | O(n^(1.3~2)) | O(1) | 原地，取决于增量序列 |
| 归并排序 | O(n log n) | O(n) | 稳定，非原地 |
| 快速排序 | O(n log n)* | O(log n) | *平均，最坏O(n²)，不稳定 |
| 堆排序 | O(n log n) | O(1) | 原地，不稳定 |
| 计数排序 | O(n + k) | O(k) | k为值域大小，稳定 |
| 基数排序 | O(d·(n + k)) | O(n + k) | d为位数，稳定 |
| 桶排序 | O(n + k)* | O(n + k) | *平均，最坏O(n²) |
| Dijkstra（优先队列） | O((V+E)·log V) | O(V) | 单源最短路径 |
| Floyd-Warshall | O(V³) | O(V²) | 全源最短路径 |
| KMP字符串匹配 | O(n + m) | O(m) | 线性时间字符串匹配 |
| 拓扑排序 | O(V + E) | O(V) | 有向无环图 |
| Prim/Kruskal最小生成树 | O(E·log V) | O(V + E) | MST算法 |
学习算法复杂度分析不仅是掌握一套数学工具，更是培养一种计算思维——在解决问题时，习惯性考虑"这个方案的规模瓶颈在哪里？""在大数据量下还能工作吗？""有没有更优的算法？"