时间复杂度与空间复杂度分析
在算法竞赛和面试中，根据题目给出的数据量大小来推断所需算法的时间复杂度和空间复杂度，是一项至关重要的核心技能。它能迅速排除掉不切实际的暴力解法，将思考方向聚焦在可行的算法上。
一、核心原理：计算机的运算速度
这个推断方法的基石是对现代计算机运算速度的一个估算。在算法竞赛平台（如 LeetCode、Codeforces、牛客网等）上，评测机通常能在 1秒内执行大约 10^7 到 10^8 次计算操作。
为了保险起见，我们通常以 10^8 作为上限参考，但更稳妥的估算是 10^7。这意味着，如果你的算法总计算量超过了这个数量级，就很可能会“超时”（Time Limit Exceeded, TLE）。
基本公式：数据规模 N 带入 时间复杂度表达式 ≈ 总计算量 ≤ 10^8
二、时间复杂度 “速查表” (Cheat Sheet)
这张表是解决算法问题的“第一直觉”，强烈建议记在心里。假设题目给出的主要数据规模是 N。
| 数据规模 N 的范围 | 可接受的时间复杂度 | 常见算法示例 |
|---|---|---|
| N ≤ 10~12 | O(N!)、O(N * 2^N) | 阶乘/指数级：全排列（Permutations）、子集生成（Subsets）、状压DP（Bitmask DP）。通常是涉及小规模暴力搜索的题目。 |
| N ≤ 18~22 | O(2^N) | 指数级：同上，状压DP、涉及所有子集的暴力搜索、折半搜索（Meet-in-the-middle）。 |
| N ≤ 50 | O(N^4) | 四次方：比较少见，可能出现在一些动态规划问题中，或者涉及四重循环的暴力解法。 |
| N ≤ 100 | O(N^3) | 三次方：Floyd-Warshall 所有点对最短路算法、三重循环的动态规划、一些涉及三维计算的几何问题。 |
| N ≤ 2,000 ~ 5,000 | O(N^2) | 二次方：基础的动态规划（如最长公共子序列）、双重循环的暴力枚举（如 Two Sum 暴力解）、Dijkstra/Prim 的朴素版、图的邻接矩阵存储下的遍历。 |
| N ≤ 10^5 ~ 10^6 | O(N log N) | 线性对数级：这是最常见的复杂度要求。高效排序算法（快速排序、归并排序）、堆（优先队列）、二分查找（Binary Search）、线段树、树状数组、Dijkstra 的堆优化版。任何需要排序预处理的题目基本都是这个复杂度。 |
| N ≤ 10^6 ~ 10^7 | O(N) | 线性级：单次遍历（数组、字符串、链表）、双指针算法（Two Pointers）、哈希表（Hash Table）、广度优先搜索（BFS）、深度优先搜索（DFS）、KMP 算法、动态规划的优化（如单调队列优化）。 |
| N ≤ 10^9 ~ 10^18 (及以上) | O(log N)、O(sqrt(N))、O(1) | 对数级/根号级/常数级： O(log N): 二分查找、快速幂、求最大公约数（GCD）。通常输入是一个很大的数字，而不是一个包含 N 个元素的数组。 O(sqrt(N)): 判断一个数是否为质数、分解质因数。 O(1): 纯数学公式或位运算。 |
三、如何进行分析：一个思考流程
当你拿到一道题时，遵循以下步骤：
立刻寻找数据范围：
- 找到题目描述最后部分的 “Constraints” 或 “数据范围” 部分。
- 关注所有变量的上限，比如数组长度
n、查询次数q、数值大小m等。
匹配速查表，确定复杂度上界：
- 将最大的
N值代入速查表，找到对应的“可接受的时间复杂度”。 - 示例：如果题目说
1 <= n <= 10^5，你的大脑应该立刻响起警报：“O(N^2)会超时，我必须寻找O(N log N)或O(N)的解法。”
- 将最大的
考虑多个变量的情况：
- 有时题目会有多个输入规模，如
N和M。 - 你需要将它们都考虑进去。例如，一个图论问题有
V个顶点和E条边。- 如果算法是
O(V * E)，你需要计算V * E的最大值是否在10^8以内。 - 如果算法是
O(V + E)，你就计算V + E的最大值。
- 如果算法是
- 有时题目会有多个输入规模，如
从复杂度反推算法类型：
O(N log N)-> 是不是需要先排序？是不是可以用二分查找？是不是可以用堆？O(N)-> 是不是可以用哈希表来优化查找？是不是可以用双指针？O(log N)-> 题目是不是具有单调性，可以用二分查找答案？是不是一个大数问题，需要用快速幂？O(2^N)-> 是不是要枚举所有状态/子集？是不是状压DP？O(N^2)-> 是不是一个动态规划问题，dp[i][j]表示某种状态？
四、空间复杂度分析
空间复杂度的限制通常比时间宽松，但同样重要。
- 常见内存限制：64MB, 128MB, 256MB。
- 估算方法：
- 一个
int(32位) 或float占用 4 字节。 - 一个
long long(64位) 或double占用 8 字节。 - 一个
char占用 1 字节。
- 一个
- 快速估算：
- 开一个
int数组a[10^6]需要10^6 * 4字节 ≈ 4MB。 - 开一个
int数组a[10^7]需要10^7 * 4字节 ≈ 40MB。 - 开一个
int二维数组dp[5000][5000]需要5000 * 5000 * 4字节 ≈ 100MB。
- 开一个
空间复杂度推断规则：
- 如果
N <= 5000，那么O(N^2)的空间（如dp[N][N]）是可行的。 - 如果
N >= 10^5，那么O(N^2)的空间绝对不可行。你必须寻找O(N)或O(log N)空间复杂度的算法。 - 注意递归深度：DFS 或递归算法的栈空间也计入空间复杂度。如果递归深度达到
N，空间复杂度就是O(N)。
五、例题
例题 1：Two Sum (两数之和)
- 题目：给定一个整数数组
nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。 - 数据范围：
2 <= nums.length <= 10^5，-10^9 <= nums[i] <= 10^9。
分析：
- 数据量：
N最大为10^5。 - 匹配速查表：
N = 10^5-> 必须是O(N log N)或O(N)。 - 排除暴力解：
O(N^2)的双重循环解法(10^5)^2 = 10^{10}，远超10^8，必定超时。 - 寻找高效解：
O(N log N)的思路？可以先排序，然后使用双指针。这是一个可行解。O(N)的思路？能否一次遍历就解决问题？我们需要快速查找target - nums[i]是否存在。什么数据结构查找快？哈希表！
- 结论：这道题的正解是使用哈希表，达到
O(N)时间复杂度和O(N)空间复杂度。
例题 2：最长上升子序列
- 题目：给定一个无序的整数数组，找到其中最长上升子序列的长度。
- 数据范围：
1 <= nums.length <= 2500。
分析：
- 数据量：
N最大为2500。 - 匹配速查表：
N = 2500->O(N^2)是可以接受的！2500^2 = 6,250,000，在10^7~10^8范围内。 - 思考算法：
O(N^2)让我立刻想到基础的动态规划。- 定义
dp[i]为以nums[i]结尾的最长上升子序列的长度。 - 状态转移方程：
dp[i] = max(dp[j]) + 1，其中0 <= j < i且nums[j] < nums[i]。 - 这个 DP 解法正好是两重循环，时间复杂度为
O(N^2)。
- 定义
- 结论：
O(N^2)的 DP 算法是这道题的可以通过的解法。
- 进阶：如果这道题的数据范围扩大到
N <= 10^5呢？O(N^2)就会超时。- 我们需要
O(N log N)的解法。这就引导我们去思考更优化的方法，比如 “耐心排序法”（patience sorting）配合二分查找。
六、常见算法和数据结构的时间与空间复杂度
表中使用的符号：
- n: 输入数据的元素数量（例如数组的长度）
- k: 数据的范围或桶的数量（例如计数排序中的最大值）
- V: 图中顶点的数量 (Vertices)
- E: 图中边的数量 (Edges)
- log n: 通常指以 2 为底的对数
1. 基础数据结构
| 数据结构 | 操作 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|---|---|
| 数组 (Array / Vector) | 访问 (Access) | O(1) |
O(1) |
O(n) |
连续内存，通过索引直接访问 |
| 搜索 (Search) | O(n) |
O(n) |
需要线性扫描 | ||
| 插入/删除 (末尾) | O(1) (摊销) |
O(n) |
动态数组在扩容时为 O(n)，但摊销后为 O(1) |
||
| 插入/删除 (中间) | O(n) |
O(n) |
需要移动后续元素 | ||
| 链表 (Linked List) | 访问/搜索 | O(n) |
O(n) |
O(n) |
需要从头节点开始遍历 |
| 插入/删除 (头部) | O(1) |
O(1) |
只需修改头指针 | ||
| 插入/删除 (尾部) | O(n)/O(1) |
O(n)/O(1) |
单链表需遍历到尾部(O(n))，若有尾指针则为 O(1) |
||
| 插入/删除 (中间) | O(1) |
O(1) |
前提是已持有该节点的前驱指针，否则查找需要 O(n) |
||
| 栈 (Stack) / 队列 (Queue) | 推入/弹出 (Push/Pop) | O(1) |
O(1) |
O(n) |
通常基于数组或链表实现 |
| 哈希表 (Hash Table) | 搜索/插入/删除 | O(1) |
O(n) |
O(n) |
最坏情况发生在所有元素哈希冲突，退化为链表/数组 |
| 二叉搜索树 (BST) | 搜索/插入/删除 | O(log n) |
O(n) |
O(n) |
平均情况对应树平衡，最坏情况对应树退化为链表 |
| 平衡二叉搜索树 (AVL, Red-Black) | 搜索/插入/删除 | O(log n) |
O(log n) |
O(n) |
通过自平衡操作保证最坏情况下的对数时间复杂度 |
| 堆 (Heap / Priority Queue) | 插入 (Insert) | O(log n) |
O(log n) |
O(n) |
将元素放入末尾再向上调整 |
| 查看最大/小值 (Peek) | O(1) |
O(1) |
根节点即为最值 | ||
| 提取最大/小值 (Pop) | O(log n) |
O(log n) |
交换头尾元素，再向下调整 | ||
| 建堆 (Heapify) | O(n) |
O(n) |
从非叶子节点开始向下调整，比逐个插入 (O(n log n)) 更快 |
||
| 字典树 (Trie / Prefix Tree) | 搜索/插入/删除 | O(L) |
O(L) |
O(N*Σ) |
L为单词长度, N为总词数, Σ为字符集大小。空间开销大 |
| 并查集 (Disjoint Set Union) | 查找 (Find) / 合并 (Union) | O(α(n)) |
O(α(n)) |
O(n) |
使用路径压缩和按秩/大小合并优化后，α(n)为反阿克曼函数，接近常数 |
2. 排序算法
| 算法 (Algorithm) | 最好时间复杂度 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 备注 |
|---|---|---|---|---|---|---|
| 冒泡排序 (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) |
稳定 | 数据基本有序时效率很高 |
| 归并排序 (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) |
不稳定 | 最坏情况是 pivot 总是选到最大/小值 |
| 堆排序 (Heap Sort) | O(n log n) |
O(n log n) |
O(n log n) |
O(1) |
不稳定 | |
| 希尔排序 (Shell Sort) | O(n) |
O(n^1.3)~`O(n²)` |
O(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+k)) |
O(d*(n+k)) |
O(d*(n+k)) |
O(n+k) |
稳定 | d为位数，k为基数 |
3. 搜索算法
| 算法 (Algorithm) | 数据结构要求 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 线性搜索 (Linear Search) | 无 | O(n) |
O(1) |
| 二分搜索 (Binary Search) | 有序数组 | O(log n) |
O(1) |
4. 图论算法
前提：图的表示方式会影响复杂度。以下复杂度主要基于 邻接表 (Adjacency List)，这是稀疏图（E 远小于 V²）的标准表示法。若使用邻接矩阵，复杂度中的 E 往往会变成 V²。
| 算法类别 | 算法 (Algorithm) | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 图遍历 | 广度优先搜索 (BFS) | O(V+E) |
O(V) |
| 深度优先搜索 (DFS) | O(V+E) |
O(V) |
|
| 单源最短路径 | Dijkstra (堆优化) | O(E log V) |
O(V) |
| Bellman-Ford | O(V*E) |
O(V) |
|
| SPFA (队列优化Bellman-Ford) | 平均 O(kE), 最坏 O(V*E) |
O(V) |
|
| 所有顶点对最短路径 | Floyd-Warshall | O(V³) |
O(V²) |
| 最小生成树 | Prim (堆优化) | O(E log V) |
O(V) |
| Kruskal (并查集) | O(E log E) 或 O(E log V) |
O(V+E) |
|
| 拓扑排序 | Kahn’s 算法 (BFS) | O(V+E) |
O(V) |
| DFS | O(V+E) |
O(V) |
5. 其他重要算法
| 算法类别 | 算法 (Algorithm) | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|---|
| 动态规划 (Dynamic Programming) | 斐波那契数列 | O(n) |
O(n)/O(1) |
O(1)空间可通过状态压缩实现 |
| 0/1 背包问题 | O(N*W) |
O(N*W)/O(W) |
N为物品数，W为背包容量。空间可压缩 |
|
| 最长公共子序列 (LCS) | O(N*M) |
O(N*M) |
N,M为两字符串长度 |
|
| 字符串匹配 | 暴力匹配 | O(N*M) |
O(1) |
|
| KMP | O(N+M) |
O(M) |
||
| 分治 (Divide and Conquer) | (作为思想，见归并/快排等) | 通常 O(n log n) |
通常 O(log n)或O(n) |
|
| 数论 | 求最大公约数 (GCD) - 欧几里得 | O(log(min(a,b))) |
O(1) |
|
| 素数筛 (Sieve of Eratosthenes) | O(n log log n) |
O(n) |
||
| 快速幂 (Exponentiation by Squaring) | O(log n) |
O(1) |
计算 a^n |
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 星海流光！
相关推荐
2025-07-28
二分查找
二分法是一种较为简单通用的搜索算法，但是在实际动手写时，却经常因为细节问题导致无法一次性写对，这里整理出了现代二分法的最佳实践写法，即红蓝染色/边界搜索算法，理解该方法后对于各种二分变种问题都能一次写对。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556"""题目描述：给定数组nums = [1, 3, 6, 6, 6, 12, 16, 19, 20]target = 6若数组中包含target，则返回数组下标，否则返回-1"""# 采用红蓝染色/边界查找法，现代二分法的最佳实践def binary_search_lower_bound(nums, target): """lower_bound问题的二分搜索写法""" left, right = -1, len(nums) ...
2025-01-06
数据结构与算法1—基本概念与复杂度
1. 算法的定义算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。 2. 算法的特性算法具有五个基本特性：输入、输出、有穷性、确定性和可行性。 2.1 输入输出算法通常具有零个或多个输入，但至少有一个或多个输出。输出的形式可以是打印输出，也可以是返回一个或多个值。 2.2 有穷性有穷性指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。 2.3 确定性确定性指算法的每一步骤都具有确定的含义，不会出现二义性。 2.4 可行性可行性指算法的每一步都必须是可行的，也就是说每一步都能够执行有限次数完成。可行性意味着算法可以转化为程序上机运行，并得到正确的结果。 3. 算法设计的要求算法设计的要求包括正确性、可读性、健壮性、高效率和低内存需求。 3.1...
2025-01-07
数据结构与算法2—数组
数组是一种常见的线性数据结构，其将相同类型的元素存储在连续的内存空间中，我们将元素在数组中的位置称为该元素的索引。 1. 数组的常用操作1.1 初始化数组初始化数组时，我们可以根据需求选用数组的两种初始化方式：无初始值、给定初始值。在未指定初始值的情况下，大多数编程语言会将数组元素初始化为0，但是经过实测，C++和C在数组为初始化时，大多数情况下不会将数组初始化为0，特别是使用new或malloc创建动态数组时数组元素都是随机值，因此在C++和C中建议创建完数组后就立刻将其初始化： 123456789101112/* 初始化数组arr */// 将数组存储在栈上int size = 5;int arr[5] = {0};printf("数组 arr = ");printArray(arr, 5);/* 初始化数组nums */// 将数组存储在栈上int nums[5] = {1, 2, 3, 4, 5};printf("数组 nums = ");printArray(nums,...
2025-05-29
回溯
回溯算法（backtracking algorithm）是一种通过穷举来解决问题的办法，其本质是一种暴力搜索算法。它的核心思想是从一个初始状态出发，暴力搜索所有可能遇到的解决方案，当遇到正确的解则将其记录，直到找到解或尝试了所有可能的选择都无法找到解为止。 框架1234567891011121314151617def backtrack(state: State, choices: list[choice], res: list[state]): """回溯算法框架""" # 判断是否为解 if is_solution(state): # 记录解 record_solution(state, res) # 不再继续搜索 return # 遍历所有选择 for choice in choices: # 剪枝：判断选择是否合法 if is_valid(state, choice): #...
2025-01-08
数据结构与算法4—列表
列表（list）是一个抽象的数据结构概念，表示元素的有序集合，支持元素访问、修改、添加、删除和遍历等操作，无需使用者考虑容量限制的问题。列表可以基于链表或数组实现。 链表天然可以看作一个列表，其支持元素增删改查操作，并且可以灵活动态扩容。 数组也支持元素增删改查，但由于其长度不可变，因此只能看作一个具有长度限制的列表。 由于数组不具备扩展长度的能力，因此可以使用动态数组来实现列表。它继承了数组的各项优点，并且可以在程序运行过程中进行动态扩容。 许多编程语言中的标准库提供的列表是基于动态数组实现的，例如Python中的list、Java中的ArrayList、C++中的vector和C#中的List等。通常，将列表和动态数组视为等同的概念。 1. 列表常用操作1.1 初始化列表列表的初始化可以采用“无初始值”和“有初始值”这两种初始化方法： 12345/* 初始化列表 */// 无初始值vector<int> nums1;// 有初始值vector<int> nums = { 1, 3, 2, 5, 4 }; 1.2...
2025-01-08
数据结构与算法3—链表
内存空间是所有程序的公共资源，在一个复杂的系统运行环境下，空闲的内存空间可能散落在内存各处。我们知道，存储数组的内存空间必须是连续的，而当数组非常大时，内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了。 链表是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”或“指针”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。 链表的设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。 链表节点ListNode除了包含值，还需额外保存一个引用（指针）。因此在相同数据量下，链表比数组占用更多的内存空间。 1. 链表结构体不同编程语言中的链表结构体如下所示： 12345/* 链表节点结构体 */typedef struct ListNode { int val; // 节点值 struct ListNode *next; // 指向下一节点的引用} ListNode; 1234567/* 链表节点 */struct ListNode { ...
评论
