Time Complexity Basics

核心概念

时间复杂度描述输入规模 n 增长时，算法工作量的增长阶。

常见复杂度：

$$O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(2^n)$$

Big-O 关注增长阶，不关注常数和低阶项。

例如：

$$3n+100=O(n)$$$$2n^2+5n+1=O(n^2)$$

---

O(log n)

如果每轮把问题规模缩小一个固定比例，例如：

i = n

while i > 1:
    i //= 2

第 k 轮：

$$i=\frac{n}{2^k}$$

停止时：

$$2^k\ge n$$

所以：

$$k=O(\log n)$$

快速识别

看到：

i *= 2
i //= 2

应优先想到：

$$O(\log n)$$

---

嵌套循环不能机械相乘

例如：

for i in range(n):
    for j in range(i):
        ...

内层每轮执行次数不同。

总次数为：

$$0+1+2+\cdots +(n-1)=\frac{n(n-1)}{2}$$

因此：

$$O(n^2)$$

不能在求和得到 O(n²) 后再额外乘一次外层 O(n)。

---

Space Complexity

空间复杂度描述输入规模增长时，算法额外占用空间的增长阶。

秋招分析时通常重点关注 Auxiliary Space，即算法为了完成计算额外申请的空间，而不是输入数据本身已经占用的空间。

常见例子：

• 只使用固定数量变量：O(1)
• 创建长度与输入规模同阶的 Hash Set：O(n)
• 递归调用最大深度为 h：Call Stack 额外空间 O(h)

因此分析算法时应同时能够回答：

Time Complexity
→ 做了多少工作

Space Complexity
→ 额外保存了多少状态

---

易错点

错误

“只要看到两层循环就是 O(n²)。”

不严谨。应该分析每一层实际执行次数。

错误

“外层 O(n)，内层总共 O(n²)，所以 O(n³)。”

如果内层的 O(n²) 已经是对所有外层执行次数求和后的结果，就不能再次乘外层。

---

Review

需要继续训练：

• 不规则嵌套循环
• 双指针复杂度
• 递归复杂度
• 时间 / 空间复杂度同时判断

Practice:

04_Practice/CS_MCQs/Data_Structure_Lesson_1.md

Mistakes:

05_Mistakes/CS.md