中 基础
时间复杂度分析#
一句话答案#
常见复杂度排序：O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(2ⁿ)，分析看循环层数和递归规模。
核心要点
| 复杂度 | 典型算法 |
|---|---|
| O(1) | 哈希查找 |
| O(logn) | 二分查找 |
| O(n) | 遍历 |
| O(nlogn) | 快排/归并 |
| O(n²) | 冒泡/嵌套循环 |
面试回答（2分钟版）
时间复杂度衡量的是算法执行时间随输入规模n的增长趋势，用大O表示法忽略常数和低阶项。常见复杂度从快到慢：O(1)哈希查找、O(logn)二分查找、O(n)线性遍历、O(nlogn)快排归并、O(n^2)冒泡和嵌套循环、O(2^n)穷举。直观感受：n=10^6时，O(n)大约一秒跑完，O(n^2)就要跑十几分钟。分析方法上，循环看嵌套层数，递归用递归树或主定理T(n)=aT(n/b)+O(n^d)。还有一个概念叫均摊复杂度，比如ArrayList扩容单次是O(n)，但均摊到每次add是O(1)。空间复杂度同理但容易忽略递归栈的空间——递归深度为d的话空间就是O(d)，比如快排递归栈平均O(logn)、最坏O(n)。
追问与易错
追问方向：
- “递归的时间复杂度怎么分析？”→ 用主定理（Master Theorem）或递归树法：画出递归树统计每层工作量再求和；如归并 T(n)=2T(n/2)+O(n) 得 O(nlogn)
- “均摊复杂度是什么？”→ 一系列操作的平均代价，允许单次操作偶尔很贵但总体廉价；典型例子是 ArrayList 扩容，单次 O(n) 但均摊到每次 add 仍是 O(1)
- “空间复杂度怎么计算？”→ 统计额外分配的空间：递归深度 × 每层栈帧大小 + 显式申请的数据结构大小；注意递归的隐式栈空间容易被忽略
易错点：
- ❌ O(logn) 和 O(n) 差距不大——量大时差距巨大
- ❌ 递归空间复杂度是 O(1)——递归栈也占空间