这六个 Python 时间复杂度的陷阱,新手几乎全中,尤其第三个.

写 Python 代码的时候，很多人觉得时间复杂度这事离自己挺远的。直到线上服务突然卡死，或者面试被问得哑口无言，才意识到掉进了坑里。新手容易踩的坑就这几个，我一个个说清楚。

1. 列表的 in 操作

很多新手写代码，习惯用 if x in list_a 来判断元素是否在列表里。列表底层是用数组存的，每次判断都要从头到尾扫一遍。数据量小的时候没感觉，列表有十万个元素，这个操作用时要几十毫秒，循环里再套一层，直接变成几秒。

正确的做法是，如果需要频繁查询元素，把列表转成集合。集合用的是哈希表，查询时间是固定值，十万个元素的集合查一次基本不花钱。我见过有人用列表存了十万个用户 ID，做去重判断时卡了五分钟，换成集合一秒不到。

2. 字符串拼接用加号

字符串在 Python 里是不可变的。你用 result = result + new_str 这种写法，每次拼接都会创建一个新字符串对象，复制旧内容再追加新内容。循环一千次就要创建一千个新字符串，复制一千次内存。一万次循环，性能损耗就很明显了。

更轻量级的做法是用列表收集所有字符串片段，最后用 ''.join(list) 一次搞定。join 方法会提前计算总长度，只创建一次字符串。我有个学生写爬虫拼接网页数据，用加号跑了三分钟，改成 join 后十秒跑完。

3. for 循环里修改列表（这个坑最多人踩）

新手喜欢在遍历列表时删除元素。比如 for item in my_list: if condition: my_list.remove(item)。这么做会出两件事。第一，remove 操作本身是 O(n) 的，它要扫描找到元素然后移动后面的全部元素。第二，遍历过程中删除元素会导致索引错乱，你会漏掉一些元素或者多删一些。

我看到过最惨的案例是有人写了个日志清洗脚本，用这种方式删除了好多不该删的日志，导致线上数据对不上。正确的做法要么用列表推导式创建新列表，要么倒序遍历删除。

4. 字典的默认值查询

很多人查字典会写成：

if key in dict: value = dict[key]

这样写查了两次字典，一次判断，一次取值。字典查询虽然快，但查两次就是浪费。更好的写法是直接用 value = dict.get(key, default_value)，只查一次。如果要做更复杂的默认值构造，用 defaultdict 或者 setdefault 方法。

别小看这一两次查询。如果你的代码每秒处理几千个请求，每次请求查几十个字典，这点差异就会累积成明显的性能瓶颈。

5. 嵌套循环没有提前跳出

两层循环嵌套，内层循环找到结果就该停了。但很多人忘记加 break 或者 return。举个实际例子，你有个用户列表，要找第一个年龄大于 30 的用户。外层循环遍历用户，内层循环检查某个条件，找到了却继续跑完整个内层循环。数据量大的时候，这个浪费就非常可观。

另外一个常见情况是盲目用两次循环解决问题，其实可以用字典把内层循环查的信息提前存好，把 O(nm) 降到 O(n+m)。我见过一个需求，两个列表找交集，有人写了两层循环跑了半天，换成集合一行搞定。

6. 递归没有记忆化

新手学递归时，写斐波那契数列最常见的就是 def fib(n): return n if n <= 1 else fib(n-1) + fib(n-2)。这种写法计算 fib(40) 就要跑几秒，因为重复计算了太多相同的子问题。用个字典或者装饰器把算过的值记下来，fib(100) 都是瞬间的事。

更隐蔽的坑是递归深度。Python 默认递归深度是 1000，超过就报错。你写动态规划或者树遍历的时候，数据量大一点就直接崩溃。改成循环或者手动管理栈才是正道。

这些坑说起来都不复杂，但每个都是我在实际项目里亲眼看到别人摔过的。代码写得多自然就记住了，新手阶段多留意点，能少熬夜查 Bug。