02.1 复杂度分析与解题框架
所属:全栈开发面试题库 / 02 数据结构与算法
覆盖范围
- 时间/空间复杂度与大 O 严格定义,最好/最坏/平均与均摊口径
- 递归复杂度:主定理、递归树、代入法与记忆化口径
- 均摊分析、常数优化、缓存友好性与局部性
- 高频解题框架:双指针、滑窗、前缀和、差分、二分、DFS/BFS、回溯、DP、单调栈/队列、哈希、堆
- 从暴力解推导最优解,时间/空间/前提的取舍表达
子主题
| 编号 | 主题 | 覆盖范围 |
|---|---|---|
| 02.1.1 | 复杂度与解题框架 | 5 个子域 90 题:大 O 与空间复杂度、递归与主定理、均摊与常数优化、高频解题框架、暴力到最优与权衡 |
面试题索引
| 编号 | 题目 | 难度 | 频率 | 所在页面 |
|---|---|---|---|---|
| 02.1.1.1-001 | 什么是时间复杂度?如何分析一段代码? | 基础 | ★★★★★ | 时间空间复杂度与大 O |
| 02.1.1.1-004 | 常见复杂度从快到慢怎么排? | 基础 | ★★★★★ | 时间空间复杂度与大 O |
| 02.1.1.1-007 | 空间复杂度怎么计算? | 基础 | ★★★★☆ | 时间空间复杂度与大 O |
| 02.1.1.1-009 | 最好、最坏、平均复杂度有什么区别? | 进阶 | ★★★★☆ | 时间空间复杂度与大 O |
| 02.1.1.2-002 | 主定理的标准形式是什么? | 高级 | ★★★★☆ | 递归复杂度与主定理 |
| 02.1.1.2-007 | 归并排序的递归复杂度怎么推? | 进阶 | ★★★★☆ | 递归复杂度与主定理 |
| 02.1.1.2-009 | 朴素斐波那契递归为什么是指数级? | 进阶 | ★★★★☆ | 递归复杂度与主定理 |
| 02.1.1.3-001 | 什么是均摊复杂度? | 高级 | ★★★★★ | 均摊分析与常数优化 |
| 02.1.1.3-002 | 动态数组翻倍扩容为什么均摊 O(1)? | 进阶 | ★★★★★ | 均摊分析与常数优化 |
| 02.1.1.3-006 | 并查集的 α(n) 是什么复杂度? | 高级 | ★★★★☆ | 均摊分析与常数优化 |
| 02.1.1.4-003 | 滑动窗口框架的固定结构是什么? | 进阶 | ★★★★★ | 高频解题框架 |
| 02.1.1.4-011 | 单调栈框架解决哪类问题? | 进阶 | ★★★★☆ | 高频解题框架 |
| 02.1.1.5-001 | 为什么面试要先讲暴力解? | 基础 | ★★★★☆ | 从暴力到最优与权衡 |
| 02.1.1.5-013 | 数据范围如何决定算法选型? | 进阶 | ★★★★☆ | 从暴力到最优与权衡 |
当前状态
- 02.1.1 已完成 5 个子主题、90 题,全部为可学习型详解。
- 页面结构:知识域首页 + 子主题页 + 分册 TOC 三层登记。
- 复杂度结论标注口径;不确定的版本行为标注待确认,未编造命令输出。