罗罗编程学习记录
本页内容 展开查看

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 三层登记。
  • 复杂度结论标注口径;不确定的版本行为标注待确认,未编造命令输出。