数据结构中的数组加倍
有时我们使用动态内存分配来创建数组。如果使用动态内存分配技术分配了数组，则可以通过执行一些操作来使数组大小加倍。
假设初始数组大小为5。
数组
| 0 | 1 | 2 | 3 | 4 |
| 元素1 | 元素2 | 元素3 | 元素4 | 元素5 |
数组加倍后，大小为-
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 元素1 | 元素2 | 元素3 | 元素4 | 元素5 | 元素6 | 元素7 | 元素8 | 元素9 | 元素10 |
要使大小为n的数组arr的大小增加一倍，请使用arr [0…n-1]。首先，我们必须创建一个新的大小为m的数组。然后将n个元素从arr复制到新数组。最后，将arr的值更改为指向新数组。
要创建大小为m的数组，这将花费θ(m)的时间。这是因为它将使用一些默认值进行初始化。然后将需要额外的θ(n)时间才能从旧阵列复制到新阵列。因此，该运算需要θ（m + n）的时间。当阵列已满时，将执行此操作。通常，m值等于2n。因此复杂度为θ（2n + n）=θ(3n)等于θ(n)。但是该操作被认为是昂贵的。但是，此操作在子序列n次迭代中摊销，然后每次迭代仅增加θ(1)时间。因此我们可以理解，以恒定因子增加数组大小不会对渐进复杂性产生不利影响。
以上是 数据结构中的数组加倍 的全部内容， 来源链接： utcz.com/z/322466.html
