c - 数组插入和删除的运行时间(Big-O)

Question

在典型的 C 数组中，为什么插入和删除操作的大 O 运行时间为 O(N)？

即以下每个操作的运行时间均为 O(N)。

• 在第 k 个元素之后插入

• 在第 N 个元素之后插入

• 移除第一个元素

• 删除第 N 个元素

数组插入和删除在执行过程中是如何发生的？如果我们要在第 k 个位置插入一个元素，为什么执行不简单地执行线性检索方法，直到到达第 k 个位置，而不是访问每个数组的元素？

Answer 1

获取元素是 O(1)，因为您确实可以随机访问，但在那之后，创建要插入的空间(或在删除的情况下进行压缩)需要 O(N) 时间。

插入:

[1,2,4,5,6]
---^ insert after this, need to move everything one step to the right.

[1,2,_,4,5,6]
-----^ insert at this location

[1,2,6,4,5,6]

删除:

[1,2,4,5,6]
---^ delete this

[1,_,4,5,6]
---^ compact to remove this "hole"

[1,4,5,6]

原因是您必须保持所有元素存储在连续位置的不变性(O(1) 中随机访问所必需的)。

为了有更好的插入和删除保证，链表更合适，因为它不需要移动元素，因为连续性和随机访问不是它的属性。