python 列表（底层为动态数组）中，按索引访问或修改元素是 o(1) 操作，而任意位置插入/删除元素为 o(n)，根本原因在于内存连续性与元素位移开销。
python 列表（底层为动态数组）中，按索引访问或修改元素是 o(1) 操作，而任意位置插入/删除元素为 o(n)，根本原因在于内存连续性与元素位移开销。
Python 列表虽常被称作“数组”，但其本质是动态数组（dynamic array）——底层使用连续的内存块存储元素，支持通过索引直接计算地址，因此访问（lst[i]）和原地修改（lst[i] = x）均为 O(1)。这是因为：
- 内存地址可由基址 +
i × 元素大小直接算出，无需遍历； - 修改不改变结构，仅更新该位置的值。
然而，在任意位置插入（如 lst.insert(i, x)）或删除（如 lst.pop(i)，非末尾）元素时，时间复杂度为 O(n)，核心原因是：
✅ 必须维持内存连续性 → 新增/删除后，索引 i 及其后的所有元素需整体平移一位；
✅ 最坏情况发生在首端（i = 0） → 所有 n 个元素均需移动，触发线性时间开销；
✅ 即使中间插入，平均仍需移动约 n/2 个元素，故统一记为 O(n)。
值得注意的是：末尾操作是特例。
-
lst.append(x)和lst.pop()（无参数）均为 O(1) 均摊时间复杂度（amortized O(1)），因为无需位移其他元素； - 底层可能偶发扩容（如从容量 8 扩至 16），此时需复制全部元素，但因扩容频率随容量指数级降低，均摊后仍为常数。
# 示例：不同操作的时间行为对比 nums = [1, 2, 3, 4, 5] # ✅ O(1)：直接读写索引位置 print(nums[2]) # 输出 3 —— 地址直接计算 nums[2] = 30 # 修改索引2处值 —— 仅写内存 # ⚠️ O(n)：非末尾插入/删除（n=5，此处移动3个元素） nums.insert(1, 99) # [1,99,2,3,4,5] → 索引1后所有元素右移 nums.pop(1) # 移除99 → 索引1后所有元素左移 # ✅ O(1)均摊：仅影响末端 nums.append(6) # 无位移，仅写入新位置 nums.pop() # 移除末尾，仅调整长度计数器
⚠️ 注意事项：
- Python 的
list不是链表，不存在“链式插入”的 O(1) 优势；若需高频首/中插删，应考虑collections.deque（双端队列，首尾 O(1)，但不支持 O(1) 索引访问）； - Big O 分析始终基于最坏情况，而非平均或最佳场景（如末尾操作快 ≠ 插入整体快）；
- “修改元素”严格指
lst[i] = value这类赋值，不包括lst[i] += 1（若涉及对象方法，复杂度取决于具体类型，但基础数值类型仍是 O(1)）。
总结：Python 列表的高效随机访问源于连续内存与索引寻址，而插入/删除的线性代价是维持这一特性的必然权衡。理解这一机制，有助于在算法设计中合理选择数据结构——需要频繁索引？用 list；需要高频中间增删？优先评估 deque 或其他结构。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
