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

02.1.1 复杂度与解题框架

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.1 复杂度分析与解题框架

这个知识域解决什么问题

算法面试先考"会不会分析",再考"能不能写对"。本知识域围绕一条主线展开:如何度量代价(时间/空间、最坏/平均/均摊)→ 如何求解递归复杂度 → 如何做均摊与常数层面的优化 → 掌握可复用的解题框架 → 从暴力解推导出最优解并说明取舍。具体题型实现见后续 02.2、02.3 及各分册章节。

知识地图

时间空间复杂度与大 O(1)
  → 递归复杂度与主定理(2)
    → 均摊分析与常数优化(3)
      → 高频解题框架(4)
        → 从暴力到最优与复杂度权衡(5)

子主题

编号 子主题 核心内容 题数
02.1.1.1 时间空间复杂度与大 O 大 O 严格定义、Ω/Θ、常见量级、循环计数、空间复杂度、最好/最坏/平均、隐藏成本、范围反推 18
02.1.1.2 递归复杂度与主定理 递归式、主定理三情形、递归树、代入法、二分/归并/快排/斐波那契、记忆化口径、栈深度 18
02.1.1.3 均摊分析与常数优化 均摊与平均区别、翻倍扩容、势能法/记账法、并查集 α(n)、局部性与缓存、装箱拆箱、常数取舍 18
02.1.1.4 高频解题框架 双指针、滑动窗口、前缀和、差分、二分、DFS/BFS、回溯、DP、单调栈/队列、哈希、堆、模拟分类 18
02.1.1.5 从暴力到最优与复杂度权衡 暴力基线、重复计算消除、有序性利用、最值结构选型、空间换时间、范围选型、溢出处理、追问应答 18

合计 90 题。 每题按「一句话结论 → 概念解释 → 原理流程 → 代码/图示 → 常见误区 → 追问(带答案)」组织;复杂度结论标注最坏/平均/均摊口径,不确定处标注待确认。

学习路径

先 1 建立大 O 与空间复杂度的度量语言,再 2 掌握递归与主定理的求解方法,然后 3 理解均摊与常数层面的性能差异,4 记牢各高频框架的触发条件与固定写法,最后 5 训练从暴力到最优的推导与取舍表达。

自检

  • [ ] 能写出大 O 的定义,并区分 O、Ω、Θ
  • [ ] 能对嵌套/顺序/对数循环正确合并复杂度
  • [ ] 能用主定理与递归树求解标准递归式
  • [ ] 能说清均摊与平均复杂度的区别,并举动态数组为例
  • [ ] 能根据题目数据范围反推可接受的复杂度量级
  • [ ] 看到问题能判断该用双指针、滑窗、前缀和、哈希、堆、单调栈还是 DP
  • [ ] 能先讲暴力复杂度,再说明优化方向与代价