数据结构中的数组加倍

有时我们使用动态内存分配创建数组。如果数组是使用动态内存分配技术分配的，我们可以通过执行一些操作来将数组的大小加倍。

假设初始数组大小为 5。

数组

数组加倍后，大小为 -

要将大小为 n 的数组 arr（arr[0…n-1]）的大小加倍。首先，我们必须创建一个大小为 m 的新数组。然后将 arr 中的 n 个元素复制到新数组中。最后，更改 arr 的值以指向新数组。

创建大小为 m 的数组需要 θ(m) 的时间。这是因为它将用一些默认值初始化。然后，它需要额外的 θ(n) 时间才能从旧数组复制到新数组。因此，该操作需要 θ(m + n) 的时间。此操作发生在数组已满时。通常，m 值与 2n 相同。因此，复杂度为 θ(2n + n) = θ(3n)，相当于 θ(n)。但此操作被认为是昂贵的。但是，此操作在后续 n 次迭代中进行摊销，则每次迭代仅增加 θ(1) 的时间。因此，我们可以理解，数组大小以常数因子增加不会对渐近复杂度产生不利影响。

Arnab Chakraborty

更新于: 2020年8月10日

2K+ 阅读量

开启你的 职业生涯

通过完成课程获得认证

开始学习