Python时间复杂度分析核心是看最耗时操作执行次数，需结合循环嵌套、递归、内置函数底层行为与输入规模n建立数量级关系，如单层遍历O(n)、两层嵌套O(n²)、二分查找O(log n)、字典查找平均O(1)、列表in操作O(n)。
Python中时间复杂度分析的核心，是看代码中**最耗时的操作执行了多少次**，而不是单纯数“写了几行”。关键在于识别循环嵌套、递归调用、内置函数的底层行为，再结合输入规模 n（比如列表长度、数字大小）建立数量级关系。
看懂常见结构的时间代价
单层 for 循环遍历长度为 n 的列表：O(n)；两层嵌套且都遍历整个列表：O(n²)；二分查找或递归减半（如归并排序拆分）：O(log n)；对字典做 key in dict 或 dict[key]：平均 O(1)，因为哈希表查表是常数时间；但对列表做 x in list 是 O(n)，需要逐个比对。
警惕“看起来简单”的隐藏开销
有些操作表面轻量，实际可能很重：
- list.append() 平均 O(1)，但偶尔触发扩容（复制所有元素）——均摊后仍是 O(1)
- list.insert(0, x) 或 list.pop(0) 是 O(n)，因为要移动后面所有元素
- sorted(list) 是 O(n log n)，而 list.sort() 原地排序也是 O(n log n)，但后者不额外占空间
-
slicing 如
lst[1:]创建新列表，O(n) 时间 + O(n) 空间
用小数据 + timeit 验证直觉
理论分析后，动手验证更可靠。不要用 time.time() 测微秒级差异，改用标准库 timeit：
立即学习“Python免费学习笔记（深入）”；
示例：比较 item in set 和 item in list
import timeit s = set(range(10000)) l = list(range(10000)) print(timeit.timeit(lambda: 9999 in s, number=100000)) # 通常 < 0.01 秒 print(timeit.timeit(lambda: 9999 in l, number=100000)) # 可能 > 1 秒
随着数据量从 1 万扩到 10 万，前者耗时几乎不变，后者明显增长——这正是 O(1) 和 O(n) 的实感差异。
写函数前先想“最坏情况怎么走”
分析时优先考虑最坏输入。比如查找函数，别只测“第一个就找到”，要想“目标在最后、或根本不存在”。递归函数注意调用深度和每次递归处理的数据量。如果函数里混用了多种结构（如遍历列表 + 对每个元素查字典），总复杂度取主导项——通常是乘积关系，例如 O(n × 1) = O(n)，但 O(n × log n) 就不能简化。
