问题求解 · #9 / 11
复杂度 + 内存模型
大 O、可变性与拷贝
为什么重要
速度和空间，正是区分"被接受的解"和"超时（TLE）的解"的关键。
核心思想
要以每单位输入规模的操作数来思考。list.append() 是均摊 O(1)；list.insert(0, x) 是 O(n)，因为后面的一切都要移位。set / dict 的查找是 O(1)；list 的成员检测（x in lst）是 O(n)。
亲眼看看 O(n²)
冒泡排序比较每一对相邻元素，并在每一趟中把最大的元素冒泡到末尾。点击 Auto 并数一数：24 个元素大约需要 200 次比较。翻倍到 48 个并不会只多花 2 倍——而是大约 4 倍。这就是 O(n²) 的样子。
comparisons: 0 swaps: 0
试一试
测一测 list 与 set 成员检测之间的差距：
import time
N = 50000
data = list(range(N))
data_set = set(data)
needles = [N - 1, N // 2, 0]
t0 = time.perf_counter()
hits_list = sum(1 for x in needles if x in data)
t1 = time.perf_counter()
hits_set = sum(1 for x in needles if x in data_set)
t2 = time.perf_counter()
print(f"list lookups: {hits_list} time: {(t1-t0)*1e6:.1f} µs")
print(f"set lookups: {hits_set} time: {(t2-t1)*1e6:.1f} µs")
浅拷贝与深拷贝——可变对象总会让人意外：
import copy
grid = [[0] * 3 for _ in range(3)]
shallow = list(grid) # same inner lists!
deep = copy.deepcopy(grid)
shallow[0][0] = 99
deep[0][0] = -1
print("grid :", grid)
print("shallow :", shallow)
print("deep :", deep)
就地修改与新对象：
# sorted() makes a new list, sort() mutates in place
nums = [3, 1, 4, 1, 5]
asc = sorted(nums) # new
nums.sort(reverse=True) # in place
print("asc :", asc)
print("nums:", nums)
快速检查
- 问： 成员检测哪个更快：列表还是集合？ 答： 集合。
小练习
- 指出哪些类型是可变的。
- 解释为什么
b = a可能很危险。
常见错误
- 错误： 以为
b = a会拷贝数据。 修正： 使用a.copy()或list(a)。 - 错误： 在函数内部无意中修改了传入的参数。 修正： 把这一点写进文档，或先拷贝一份。
关键要点
list.append()均摊 O(1)；list.insert(0, x)是 O(n)。x in set/x in dict是 O(1)；x in list是 O(n)。list(other)是浅拷贝——内层的可变对象仍然是共享的。copy.deepcopy是正确的但很慢；只在需要完全隔离时才用。