计算动态数组的时间复杂度 [英] Calculating Time Complexity of a Dynamic Array

问题描述

计算基于动态数组的时间复杂度。

Calculating Time complexity of a Dynamic Based Array.

在本文中，我读到它提到了两种动态增加数组的方法。

In the text i am reading it mentions two approaches for dynamically increasing an array.

动态阵列方法1

第一种方法说明您可以构造一个大小为1的数组，并在每次将新数据推入数组时动态增加。例如，如果您推送新数据，那么您将创建一个新数组，其大小为该数组的旧大小加1，然后将所有元素从旧数组复制到新数组中，然后添加新数据。文本表明这种方法的时间复杂度为0（N ^ 2）。我不确定怎么办？我认为时间复杂度为O（N），因为您要为每个新元素创建一个新数组，其中可以有N个新元素，并且您要复制的旧元素又近似于N。因此，我认为复杂度为O（N）。

The first approach states that you can construct an array of size 1 and dynamically increase it for every time you push a new data to the array. For instance if you push new data then you create a new array of old size of the array plus 1 and copy all the elements from the old array to the new one and then add the new data. The text is suggesting that time complexity for this approach is 0(N^2). I am not sure how though? I thought the time complexity is O(N) since you are creating a new array for every new element where you can have N new elements and also you are copying the old elements which is again approximated to N. Therefore i would think that complexity is O(N).

动态阵列方法2

第二种方法是建议我们可以通过在阵列每次满时将其容量加倍来降低时间复杂度。例如，如果我们有一个初始容量为4的数组，并且已将其装满，那么在尝试添加新数据时，我们将创建一个大小为8的新数组，并将所有旧元素复制到该新数组中，然后添加新数据。

The second approach is suggesting that we can reduce time complexity by doubling the capacity of the array every time it is full. For instance if we have an array of initial capacity size 4 and we make it full then when attempting to add new data we would create a new array of size 8 and copy all the old elements to this new array and then add the new data.

文本进一步指出，此方法的时间复杂度为O（N）。

The text further states that the time complexity for this approach is O(N).

有人可以吗？阐明该方法的时间复杂度如何也为O（N）？

Can someone please clarify how is the time complexity for the approach also O(N) ?

推荐答案

想象一下，一个数组以一个空间开始1个项目，我们将继续添加N个项目，一次添加1个。第一次，我们必须将1个项目复制到更大的空间中，第二次我们将2个项目复制，以此类推。在添加第N个项目之前，我们需要复制N-1个现有项目，因此总体而言，我们已经完成了

Imagine that one starts with an array with space for 1 item and that we proceed to append N items, 1 at a time. The first time we have to copy 1 item to the larger space, the second time 2 items and so on. Before adding the Nth item we need to copy the N-1 existing items, so overall we've done

1 + 2 + 3 + ... N-1 = N(N-1)/2

因此，是O（N ^ 2）

Copies, so this is O(N^2)

使用第二种方法，我们复制的频率要少得多：添加这些项目时，第一和第二个副本会发生，但是下一个副本不会直到大小为4的缓冲区已满，然后是大小为8的缓冲区已满之后，再执行一个。

With the second approach we copy far less often: the first and second copies happen as we add those items, but then the next copy doesn't happen until a size 4 buffer is full and the one after that when a size 8 buffer is full.

如果k等于2 ^（k-1） < N< = 2 ^ k那么我们会

If k is such that 2^(k-1) < N <= 2^k then we'd do

1 + 2 + 4 + 8 + ... 2^(k-1) = 2^k - 1 

份，即为O（N）

这篇关于计算动态数组的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！