20 分钟

求职冲刺

复杂度分析

理解时间和空间复杂度

理解大O表示法
分析常见算法复杂度
识别代码效率

大O表示法

示例代码（可运行）

Python 0%

1# 不同复杂度的运行时间对比

2import time

4def o_n(n):

5 """O(n): 线性"""

6 total = 0

7 for i in range(n):

8 total += i

9 return total

11def o_n2(n):

12 """O(n²): 平方"""

13 count = 0

14 for i in range(n):

15 for j in range(n):

16 count += 1

17 return count

19def o_log_n(n):

20 """O(log n): 对数（二分）"""

21 count = 0

22 while n > 1:

23 n //= 2

24 count += 1

25 return count

27for n in [100, 1000, 10000]:

28 start = time.time()

29 o_n(n)

30 t1 = time.time()-start

31 start = time.time()

32 o_n2(n)

33 t2 = time.time()-start

34 print(f"n={n}: O(n)={t1:.5f}s O(n²)={t2:.4f}s")

36print(f"\n二分次数 O(log n): n=100万→{o_log_n(1000000)}次")

常见复杂度排序

示例代码（可运行）

Python 0%

1print("复杂度从快到慢：")

2complexities = [

3 ("O(1)", "常数", "数组访问、字典查找"),

4 ("O(log n)", "对数", "二分查找"),

5 ("O(n)", "线性", "遍历列表"),

6 ("O(n log n)", "线性对数", "排序（快排/归并）"),

7 ("O(n²)", "平方", "嵌套循环、冒泡排序"),

8 ("O(2^n)", "指数", "暴力递归"),

10for name, label, example in complexities:

11 print(f" {name:12s} {label:6s} 例：{example}")

预测输出

print(1000000 in set(range(100)))

找 BugO(n²)嵌套循环，用set可优化到O(n)。

def has_duplicate(lst): for i in range(len(lst)): for j in range(i+1,len(lst)): if lst[i]==lst[j]: return True return False

填空题填写空白处的代码

二分查找的时间复杂度是O( n)

选择题

字典d[key]查找的复杂度？

资深工程师加餐

底层原理 · 大厂视角 · 工程经验，点卡片展开

时间复杂度看「基本操作次数随输入规模 n 的增长量级」，空间复杂度看额外占用的内存；还要区分最好、最坏、平均与均摊。面试时先给能工作的暴力解并说明其复杂度，再一步步优化到更优——面试官评估的往往是你的推导过程，而不只是你是否背出了最优答案。

挑战任务

复杂度挑战

简单+50 XP

分析三种求和方法的复杂度。

复杂度挑战

Python 0%

2 个测试用例

课后作业

优化查找

中等+20 XP

将O(n²)的重复检查优化为O(n)。

优化查找

Python 0%

1 个测试用例