常见算法的时间复杂度
一、常见算法时间复杂度速查表
| 算法类别 | 具体算法 | 最佳情况 | 平均情况 | 最坏情况 | 空间复杂度 (通常) | 关键特点/说明 |
|---|---|---|---|---|---|---|
| 排序算法 | ||||||
| 冒泡排序 (Bubble Sort) | O(n) (优化后) | O(n²) | O(n²) | O(1) | 简单，效率低，原地排序 | |
| 选择排序 (Selection Sort) | O(n²) | O(n²) | O(n²) | O(1) | 简单，效率低，交换次数少，原地排序 | |
| 插入排序 (Insertion Sort) | O(n) (已有序) | O(n²) | O(n²) | O(1) | 小规模或基本有序数据高效，原地排序 | |
| 希尔排序 (Shell Sort) | O(n log n) | 取决于间隔序列 | O(n²) | O(1) | 插入排序改进版，不稳定 | |
| 归并排序 (Merge Sort) | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定，高效，分治典范，需额外空间 | |
| 快速排序 (Quick Sort) | O(n log n) | O(n log n) | O(n²) (坏划分) | O(log n) (递归栈) | 通常最快，分治，原地排序，最坏情况依赖划分 | |
| 堆排序 (Heap Sort) | O(n log n) | O(n log n) | O(n log n) | O(1) | 原地排序，不稳定 | |
| 计数排序 (Counting Sort) | O(n + k) | O(n + k) | O(n + k) | O(n + k) | 非比较排序，k是数据范围，范围小高效 | |
| 桶排序 (Bucket Sort) | O(n + k) | O(n + k) | O(n²) (坏分布) | O(n + k) | 非比较排序，数据分布均匀高效 | |
| 基数排序 (Radix Sort) | O(d*(n + b)) | O(d*(n + b)) | O(d*(n + b)) | O(n + b) | 非比较排序，d是位数，b是基数(桶数)，稳定 | |
| 搜索算法 | ||||||
| 线性搜索 (Linear Search) | O(1) (第一个) | O(n) | O(n) | O(1) | 无序数组 | |
| 二分查找 (Binary Search) | O(1) (中间) | O(log n) | O(log n) | O(1) (迭代) | 必须有序数组，分治思想 | |
| 数据结构操作 | ||||||
| 数组 | ||||||
| 访问 (by index) | O(1) | O(1) | O(1) | - | ||
| 插入/删除 (末尾) | O(1) (摊销) | O(1) (摊销) | O(1) (摊销) | - | 动态数组扩容有摊销成本 | |
| 插入/删除 (中间/开头) | O(n) | O(n) | O(n) | - | 需要移动元素 | |
| 搜索 (无序) | O(n) | O(n) | O(n) | - | ||
| 搜索 (有序) | O(log n) | O(log n) | O(log n) | - | 二分查找 | |
| 链表 (单/双) | ||||||
| 访问 (by index) | O(n) | O(n) | O(n) | - | 需要遍历 | |
| 插入/删除 (已知位置) | O(1) | O(1) | O(1) | - | 前提是已获得要操作节点的引用 | |
| 插入/删除 (头/尾) | O(1) | O(1) | O(1) | - | 通常维护头尾指针 | |
| 搜索 | O(n) | O(n) | O(n) | - | 需要遍历 | |
| 哈希表 (HashMap/Dict) | ||||||
| 插入 (Insert) | O(1) (摊销) | O(1) (摊销) | O(n) (全冲突) | - | 理想情况O(1)，冲突处理影响效率 | |
| 查找 (Lookup) | O(1) (摊销) | O(1) (摊销) | O(n) (全冲突) | - | 理想情况O(1)，冲突处理影响效率 | |
| 删除 (Delete) | O(1) (摊销) | O(1) (摊销) | O(n) (全冲突) | - | 理想情况O(1)，冲突处理影响效率 | |
| 平衡二叉搜索树 (AVL, RB) | ||||||
| 插入 (Insert) | O(1) | O(log n) | O(log n) | O(log n) (递归栈) | 自平衡保证O(log n) | |
| 查找 (Search) | O(1) (根) | O(log n) | O(log n) | O(log n) (递归栈) | 自平衡保证O(log n) | |
| 删除 (Delete) | O(1) (叶子) | O(log n) | O(log n) | O(log n) (递归栈) | 自平衡保证O(log n) | |
| 二叉堆 (优先队列) | ||||||
| 插入 (Insert) / 入队 (Enqueue) | O(1) (摊销) | O(log n) | O(log n) | - | 堆化 (Heapify Up) | |
| 取最小/最大 (Find Min/Max) | O(1) | O(1) | O(1) | - | 查看根节点 | |
| 删除最小/最大 (Extract) | O(log n) | O(log n) | O(log n) | - | 堆化 (Heapify Down) | |
| 构建堆 (Heap Build) | O(n) | O(n) | O(n) | - | Floyd算法，自底向上堆化 | |
| 图算法 | ||||||
| 广度优先搜索 (BFS) | O(V + E) | O(V + E) | O(V + E) | O(V) | 邻接表或邻接矩阵（需转换） | |
| 深度优先搜索 (DFS) | O(V + E) | O(V + E) | O(V + E) | O(V) (递归栈) | 邻接表或邻接矩阵（需转换） | |
| Dijkstra (无负权) | O(V log V + E) | O(V log V + E) | O(V log V + E) | O(V) | 优先队列 (堆) 优化后 | |
| Bellman-Ford (可有负权) | O(V*E) | O(V*E) | O(V*E) | O(V) | 检测负权环 | |
| Floyd-Warshall (APSP) | O(V³) | O(V³) | O(V³) | O(V²) | 所有节点对最短路径，动态规划 | |
| Prim (MST - 邻接矩阵) | O(V²) | O(V²) | O(V²) | O(V) | ||
| Prim (MST - 邻接表+堆) | O(E log V) | O(E log V) | O(E log V) | O(V) | 优先队列 (堆) 优化后 | |
| Kruskal (MST) | O(E log E) | O(E log E) | O(E log E) | O(E+V) | 并查集优化后，主要成本在排序边(E log E) | |
| 字符串匹配 | ||||||
| 朴素算法 (Brute Force) | O(n) (首字符) | O((n-m+1)*m) | O(n*m) | O(1) | n=文本长， m=模式长 | |
| KMP (Knuth-Morris-Pratt) | O(n + m) | O(n + m) | O(n + m) | O(m) | 预处理O(m)，匹配O(n) | |
| Rabin-Karp | O(n + m) | O(n + m) | O(n*m) (坏哈希) | O(1) | 基于哈希，平均好，最坏差(哈希冲突) |
二、时间复杂度推断核心技巧 (如何分析？)
分析时间复杂度关键在于找出基本操作执行次数 T(n) 与输入规模 n 之间的函数关系，然后用大O表示法简化（忽略常数、系数、低阶项）。
以下是实用的推断技巧：
- 聚焦循环 (Loops are Key):
- 单层循环： 循环体执行次数通常与
n线性相关 ->O(n)。for i in range(n): # 循环 n 次 do_something() # O(1) 操作 # T(n) = n * O(1) = O(n) - 嵌套循环： 分析每一层循环的迭代次数。
- 独立嵌套： 内层循环次数固定或与外层无关 -> 相乘。
for i in range(n): # 循环 n 次 for j in range(10): # 固定循环 10 次 (常数) do_something() # O(1) # T(n) = n * 10 * O(1) = O(n) - 相关嵌套： 内层循环次数依赖于外层循环变量 -> 通常是求和。
for i in range(n): # i 从 0 到 n-1 for j in range(i, n): # j 从 i 到 n-1 -> 执行 (n - i) 次 do_something() # O(1) # T(n) = Σ(i=0 to n-1) Σ(j=i to n-1) 1 = Σ(i=0 to n-1) (n - i) # = n + (n-1) + ... + 1 = n(n+1)/2 = O(n²) - 多重嵌套： 嵌套层数
k层，且每层大致循环n次 ->O(n^k)。for i in range(n): for j in range(n): for k in range(n): do_something() # O(1) # T(n) = n * n * n * O(1) = O(n³)
- 独立嵌套： 内层循环次数固定或与外层无关 -> 相乘。
- 单层循环： 循环体执行次数通常与
- 理解递归 (Recursion Requires Equations):
- 递归算法的时间复杂度分析通常需要建立递归方程并求解。
- 主定理 (Master Theorem)： 解决形如
T(n) = a * T(n/b) + f(n)的递归方程。这是分析分治算法（如归并、快排、二分查找）的利器。主定理根据f(n)与n^(log_b(a))的关系给出解：f(n) = O(n^(log_b(a) - ε))(ε > 0) ->T(n) = Θ(n^(log_b(a)))f(n) = Θ(n^(log_b(a)))->T(n) = Θ(n^(log_b(a)) * log n)f(n) = Ω(n^(log_b(a) + ε))(ε > 0) 且a*f(n/b) <= c*f(n)(c<1) ->T(n) = Θ(f(n))
- 递归树 (Recursion Tree)： 可视化递归调用过程，计算每层工作量和总层数。
- 例如斐波那契
F(n) = F(n-1) + F(n-2)，递归树是二叉树，节点数约2^n->O(2^n)。
- 例如斐波那契
- 展开/代入法 (Iteration/Substitution)： 反复将递归式右边的
T(...)用定义展开，观察规律或求和。
- 识别分治 (Divide and Conquer Pattern):
- 模式：将问题分成
a个大小为n/b的子问题，合并结果代价为f(n)。 - 时间复杂度通式：
T(n) = a * T(n/b) + f(n)-> 用主定理分析。 - 经典例子：
- 二分查找：
T(n) = T(n/2) + O(1)->a=1, b=2, f(n)=O(1)->O(log n)(Case 2)。 - 归并排序：
T(n) = 2T(n/2) + O(n)->a=2, b=2, f(n)=O(n)->O(n log n)(Case 2)。 - 快速排序 (平均)：
T(n) = T(k) + T(n-k-1) + O(n)，假设划分均衡k≈n/2->≈ 2T(n/2) + O(n)->O(n log n)(Case 2)。最坏划分k=0 或 k=n-1->T(n) = T(n-1) + O(n)->O(n²)。
- 二分查找：
- 模式：将问题分成
- 关注数据结构和操作 (Data Structures Matter):
- 不同数据结构的同一操作（如查找、插入、删除）时间复杂度可能天差地别。
- 关键问题：
- 这个操作需要遍历多少元素？(线性搜索 vs 二分查找 vs 哈希查找)
- 这个操作需要移动多少元素？(数组中间插入 vs 链表已知位置插入)
- 这个操作需要维护什么额外结构？(堆插入后需要堆化
O(log n)，平衡树插入后可能需要旋转O(log n))
- 例子： 在已排序数组中查找 ->
O(log n)(二分)，在哈希表中查找 ->O(1)(平均)，在链表中查找 ->O(n)。
- 注意“隐藏”成本 (Watch for Hidden Costs):
- 函数调用： 递归调用、辅助函数调用会增加栈开销，影响实际常数因子，但不改变大O阶（除非递归深度很大，如链表递归
O(n)深度）。 - 内存分配： 动态数组扩容 (
append的摊销O(1))。 - 内置操作： 某些语言的内置操作可能不是
O(1)。例如 Python 的len(list)是O(1)（列表存储了长度），而min(list)是O(n)。
- 函数调用： 递归调用、辅助函数调用会增加栈开销，影响实际常数因子，但不改变大O阶（除非递归深度很大，如链表递归
- 考虑输入特征 (Consider Input Characteristics):
- 最好/最坏/平均： 明确分析的是哪种情况。快排最坏
O(n²)，平均O(n log n)。 - 数据分布： 桶排序、计数排序的效率高度依赖输入数据的范围或分布。
- 问题规模：
n代表什么？是数组长度、节点数、边数、还是数值大小？分析T(n)时n必须一致。
- 最好/最坏/平均： 明确分析的是哪种情况。快排最坏
- 利用已知结论 (Leverage Known Results):
- 记住常见算法和操作的复杂度（如排序下限
O(n log n)，堆操作O(log n)，BFS/DFSO(V+E)）。 - 组合操作：如果算法由多个步骤组成，总复杂度由最高阶的步骤决定（
O(n²) + O(n log n) + O(n) = O(n²)）。
- 记住常见算法和操作的复杂度（如排序下限
三、核心推断步骤总结
- 定义
n： 明确输入规模n指什么（数组长度？节点数？数值位数？）。 - 识别基本操作： 找到执行最频繁、最耗时的核心操作（比较、赋值、算术、特定函数调用）。
- 计算
T(n)：- 对于循环：分析循环次数（单层、嵌套层数、迭代次数关系）。
- 对于递归：建立递归方程，使用主定理、递归树或代入法求解。
- 对于分治：识别
a,b,f(n)，应用主定理。 - 考虑数据结构的固有操作成本。
- 简化到大O： 忽略常数因子、系数、低阶项，保留最高阶项。
- 明确情况： 说明是最好、最坏还是平均时间复杂度。
