Python时间复杂度核心是分析基本操作执行次数随输入规模n的增长趋势，需识别循环嵌套、递归深度及数据结构访问方式；列表索引、字典取值为O(1)，列表查找为O(n)，排序为O(n log n)，斐波那契递归为O(2ⁿ)。
看Python时间复杂度，核心是数“基本操作执行次数”怎么随输入规模 n 变化，而不是看代码行数或运行几秒。关键在识别循环嵌套、递归深度、数据结构访问方式这些结构性特征。
盯住输入规模 n 和最内层操作
先明确什么是 n：通常是列表长度、数组大小、字符串字符数等可变的输入量。然后从最内层开始，看某条关键语句（比如比较、赋值、访问）被执行了多少次。
- 单层
for x in lst:→ 最多执行 n 次 → 常见为 O(n) - 两层嵌套，且都遍历整个
lst→ 执行约 n × n = n² 次 → 典型 O(n²)（如冒泡排序） - 每次把问题规模砍掉一半（如二分查找），重复直到剩1个 → 大概执行 log₂n 次 → O(log n)
忽略常数和低阶项，只留最高阶
大O描述的是增长趋势，不是精确计时。例如：
-
total = 0; for i in range(n): total += i * 2 + 5→ 实际操作次数是 3n + 1，但写成 O(n) -
for i in range(n): for j in range(n//2): ...→ 是 n × (n/2) = n²/2，仍为 O(n²) -
def f(n): return n**2 + 100*n + 1000→ 时间复杂度是 O(n²)，不写 O(n² + 100n + 1000)
记住常见操作的默认复杂度
Python内置操作不是都一样快，查表能省大量分析时间：
立即学习“Python免费学习笔记（深入）”；
- 列表索引
lst[i]、字典取值d[key]、集合查询x in set_s→ 都是 O(1)（平均情况） - 列表中用
x in lst查找 → 要逐个比，O(n) - 切片
lst[:k]→ 创建新列表，耗时 O(k)；若 k ≈ n，则是 O(n) - 排序
sorted(lst)或lst.sort()→ 底层是 Timsort，O(n log n)
递归算法重点看调用树深度和每层工作量
比如快速排序：每次选基准分割，理想情况下每层处理总长 n 的数据，共约 log n 层 → O(n log n)；最坏（已排序）下变成 n 层，每层仍做 O(n) 工作 → O(n²)。
再如斐波那契递归：fib(n) = fib(n-1) + fib(n-2)，调用树节点数接近 2ⁿ → O(2ⁿ)，明显低效。
