python列表底层是动态数组，支持o(1)的任意索引访问/修改，但任意位置插入或删除为o(n)；仅在末尾增删时可达o(1)，因无需移动其他元素。
python列表底层是动态数组，支持o(1)的任意索引访问/修改，但任意位置插入或删除为o(n)；仅在末尾增删时可达o(1)，因无需移动其他元素。
在Python中，list 类型虽常被称作“列表”，但其底层实现是动态数组（dynamic array）——即一段连续分配的内存空间，元素按索引顺序紧邻存储。这一物理结构直接决定了各类操作的时间复杂度特性。
✅ 为什么访问/修改任意元素是 O(1)？
因为数组支持基于偏移量的直接寻址：给定索引 i，内存地址可由公式 base_address + i * element_size 瞬间算出，无需遍历。无论 i 是 0、100 还是 len(lst)-1，CPU 都能一次定位并读写。
nums = [10, 20, 30, 40] print(nums[2]) # → 30，O(1) nums[2] = 35 # 修改，O(1)
❌ 为什么在任意位置插入/删除是 O(n)？
关键在于内存连续性约束。当在索引 i 处插入新元素时：
- 若
i ，需将原索引i到len(lst)-1的所有元素整体右移一位； - 若删除
i处元素，则需将i+1到末尾的所有元素整体左移一位。
该移动过程涉及n−i次赋值操作，最坏情况（i=0，首部操作）需移动全部n个元素，故为 O(n)。
nums = [10, 20, 30, 40] nums.insert(1, 15) # 在索引1处插入 → [10,15,20,30,40] # 实际执行：20→索引2，30→索引3，40→索引4（3次移动）
✅ 末尾操作为何是 O(1)？
在列表末尾追加（append()）或弹出（pop()）元素时：
-
append()：若预留容量足够，直接写入len(lst)位置，无移动； -
pop()（无参数）：直接移除最后一个元素，也不影响其余索引。
二者均只操作单个位置，属常数时间。Python列表内部维护了size和allocated字段，通过倍增策略（如扩容至1.125×当前容量）摊还了扩容成本，使append()均摊复杂度仍为 O(1)。
nums.append(50) # O(1) 均摊 nums.pop() # O(1)
⚠️ 注意事项
-
不要混淆
pop(i)和pop()：pop(0)删除首元素是 O(n)，而pop()（默认删末尾）是 O(1)； -
del lst[i]、lst[i:j] = []等切片删除同样触发移动，均为 O(n)； - 若需高频首部/中部增删，应考虑
collections.deque（双端队列，首尾操作均为 O(1)），但其不支持 O(1) 随机访问； - Big O 描述的是最坏情况渐近上界，不反映平均或最佳表现——例如
insert(len(lst), x)实际很快，但复杂度仍记为 O(n)，因其无法保证所有输入都快。
理解这一机制，有助于在算法设计中合理选择数据结构：用 list 优先保障随机访问效率，用 deque 或链表思想优化频繁中间修改场景。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
