[L1] 常见数据结构基础操作的时间复杂度是多少？

一句话结论

各结构复杂度由内部组织方式决定，选型前须熟记增删查速查表。

体系讲解

五类结构速查表

结构	随机访问	头部插入	尾部追加	按值查找	任意删除
数组	O(1)	O(n)	O(1) 均摊	O(n)	O(n)
链表（双向）	O(n)	O(1)	O(1)*	O(n)	O(1)**
哈希表	—	—	O(1) 均摊	O(1) 均摊	O(1) 均摊
二叉搜索树（BST）	—	O(log n) 均摊	—	O(log n) 均摊	O(log n) 均摊
二叉堆	—	O(log n)	O(log n)	O(1) 仅堆顶	O(log n)

* 需持有尾指针；** 需预先持有目标节点指针（不含查找耗时）

各结构核心特征

• 数组：连续内存，按索引 O(1) 访问；插入/删除需移动后续元素，头部操作代价最高。
• 链表：节点分散，顺序遍历才能定位；已知节点的插入/删除是 O(1)，代价在"找到节点"。
• 哈希表：键值映射，均摊 O(1) 是哈希均匀分布的前提；最坏（所有 key 碰撞）退化为 O(n)。
• BST：有序树，均摊 O(log n)；退化（单边链表）最坏 O(n)，平衡 BST（AVL/红黑树）可保证 O(log n)。
• 二叉堆：只保证堆顶（最大/最小值）O(1) 访问；插入/删除须调整堆结构（heapify），O(log n)。

选型速查

主要操作	推荐结构
频繁按索引访问	数组
频繁头部插入/删除	链表
按键快速查找	哈希表
需要维护有序性	BST / 排序数组
反复取最大/最小值	堆（优先队列）

考察意图

验证候选人是否具备最基础的数据结构选型判断力；所有算法题的前置语言——答不出"哈希表查找是 O(1)"，后续讨论无从展开。

追问链

1. PHP 的 array_unshift() 是 O(1) 还是 O(n)？
   简答：O(n)。PHP 数组底层是 HashTable，头部插入后需将所有整数 key 全部重新偏移（re-index），整体是线性操作；array_push() / $arr[] = 则是 O(1) 均摊。

2. 哈希表 O(1) 的前提是什么？退化条件是什么？
   简答：前提是哈希函数分布均匀、负载因子合理（通常 < 0.75）。极端情况下所有 key 哈希到同一 bucket，退化为链表遍历，最坏 O(n)；PHP 的 HashTable 通过哈希函数散列与动态扩容维持均匀分布（⚠️ 需查证：具体哈希算法实现随版本可能变动）。

3. 为何说"链表删除是 O(1)"，但 LeetCode 里删除链表节点经常要 O(n)？
   简答：O(1) 的前提是已持有目标节点的指针（以及前驱指针，双向链表）。如果需要先按值遍历找节点，查找本身就是 O(n)；把"找到"和"删除"分开看，两步合计仍是 O(n)。

易错点

1. 把"均摊 O(1)"当严格 O(1)：哈希表查找/插入、数组 append 都是均摊 O(1)，单次扩容操作本身是 O(n)；高并发写入场景下扩容抖动需关注。
2. BST 默认等同平衡 BST：朴素 BST 按序插入会退化为 O(n) 单链；面试说 O(log n) 需补充"前提是平衡树（AVL/红黑树）"。
3. 链表删除忽略"找节点"代价：经常把"删除操作 O(1)"误用于"按值删除"的整体分析，导致复杂度计算偏低。

代码示例

<?php
// PHP 数组：尾部追加 O(1) 均摊 vs 头部插入 O(n)
$arr = range(1, 5);
$arr[] = 6;            // O(1) 均摊 — 尾部追加
array_unshift($arr, 0); // O(n)   — 头部插入，全部整数 key 重新偏移

// 哈希表：O(1) 均摊查找
$map = ['uid_1' => 'Alice', 'uid_2' => 'Bob'];
$exists = isset($map['uid_1']); // O(1) 均摊

// 堆排序取 Top-1（最小值），O(1) 访问堆顶
$heap = new SplMinHeap();
foreach ([5, 3, 8, 1] as $v) $heap->insert($v); // 每次 O(log n)
echo $heap->top(); // O(1)，输出 1