信息技术大学
复杂度分析
数据结构与算法·面试高频 · 第 1 章 复杂度与线性结构
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
信息技术大学
复杂度分析
数据结构与算法·面试高频 · 第 1 章 复杂度与线性结构
大 O 记号与推导
大 O 只看增长趋势：忽略常数与低阶项，问的是「数据翻倍，耗时怎么涨」。
定义
增长率上界，取最高阶项、忽略系数
推导法
循环嵌套相乘，顺序执行取最大者
常见坑
藏在函数调用与切片拷贝里的隐性开销
常见复杂度量级对比
从 O(1) 到 O(n!)：对数与线性是朋友，指数与阶乘是敌人。
O(1)/O(log n)
哈希查找、二分定位，数据翻倍只多一步
O(n)/O(n log n)
遍历与高效排序，可接受的主力区间
O(2^n) 起
子集枚举起步，n 到 20 就要报警
递归复杂度与主定理
递归成本 = 子问题数 × 规模 ÷ 分割比 + 每层开销：主定理一个公式定调。
递归式
T(n)=aT(n/b)+f(n)：a 路递归，规模切 1/b
主定理
比较 f(n) 与 n^log_b a，谁占大头听谁的
套例
归并排序 a=2、b=2、f(n)=n 同阶，O(n log n)
均摊分析
一次贵不等于次次贵：动态扩容的插入，均摊到每次仍是 O(1)。
均摊
偶尔的昂贵操作摊到一整串操作上
典型
动态数组扩容、双栈实现队列的摊还
本节要点
- ✓大 O 看趋势，忽略常数低阶项
- ✓n log n 是排序门槛，2^n 要报警
- ✓主定理：比 f(n) 与 n^log_b a
- ✓均摊：偶尔贵，次次平
延伸主题：给老代码估复杂度推一遍快排期望复杂度
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1O(n log n) 与 O(n²) 在 n=100 万时差多少量级？
参考答案n log n 约两千万次操作，毫秒到几十毫秒级；n² 是万亿级，分钟起步。数据规模一大，多项式阶的一层之差就是可用与不可用的分界。
2为什么说「均摊 O(1)」不是安慰剂？
参考答案扩容单次 O(n)，但 n 次插入才触发一次，总成本 O(n)，严格按操作序列均摊每次 O(1)；且任何输入序列都无法让它每次都扩容，这是证明不是概率。
3递归树与主定理什么关系？主定理失效怎么办？
参考答案主定理是递归树逐层求和的快捷公式，只覆盖 f(n) 与子问题项可比的几种情形；不可比时画递归树逐层求和，或用数学归纳代入验证，慢但通用。