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

Running Time (Big-O) of Array Insertion and Deletion

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

即以下每个操作都有 O(N) 运行 时间。

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

获取元素是 O(1) 因为你确实有随机访问,但之后,创建 space 插入(或压缩以防删除) 需要 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) 中随机访问所必需的)。

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