关于数据结构插入删除操作时间复杂度分析的疑问

1. 删除操作的时间复杂度：要不要算查找步骤？ #

这得看具体场景：

• 如果已经直接拿到待删除元素的索引或节点引用（比如知道数组下标，或者链表中拿到了目标节点的指针），那时间复杂度只算修改指针、移动元素这类删除动作本身。比如链表删除已知节点是O(1)，数组删除末尾元素是O(1)，删除中间元素则是O(N)（因为要移动后续元素）。
• 如果需要先查找待删除元素（比如要删除链表中值为x的节点，或者无序数组中找某个特定元素），那查找的时间必须算进总复杂度。比如无序链表找元素是O(N)，加删除的O(1)，整体就是O(N)；有序数组用二分查找找位置是O(logN)，但删除时移动元素是O(N)，总复杂度还是O(N)。

2. 插入操作的时间复杂度：要不要算查找插入位置？ #

同样分场景判断：

• 如果直接指定插入位置（比如数组末尾插入、链表头部/尾部插入，或者明确知道要插入的位置），只需要计算插入动作本身的时间。比如数组末尾插入（空间足够时）是O(1)，链表头部插入是O(1)。
• 如果需要先查找合适的插入位置（比如有序数组要维持有序，插入前得找到对应位置；有序链表同理），那查找的时间必须计入总复杂度。比如有序数组用二分查找找位置是O(logN)，但插入时移动元素是O(N)，总复杂度还是O(N)；有序链表找位置是O(N)，加插入的O(1)，整体是O(N)。

为什么数组插入的复杂度有O(1)和O(N)两种标注？ #

这是因为场景不同：

• 标注O(1)的情况：一般指数组末尾插入，且不考虑扩容开销（默认数组空间足够）。此时只需要把元素放到最后一个空位，一步完成。
• 标注O(N)的情况：要么是在数组中间/头部插入，需要移动后面所有元素腾出位置；要么是考虑数组扩容的最坏情况（数组满了之后，要重新申请更大的空间，把原有元素全部复制过去，这一步复制是O(N)，再加上插入的O(1)，总复杂度就是O(N)）。

内容的提问来源于stack exchange，提问作者miiky123