计算动态数组的时间复杂度
Calculating Time Complexity of a Dynamic Array
正在计算基于动态的数组的时间复杂度。
在我正在阅读的文本中，它提到了两种动态增加数组的方法。
动态数组方法 1
第一种方法指出，您可以构造一个大小为 1 的数组，并在每次将新数据推送到该数组时动态增加它。例如，如果您推送新数据，那么您将创建一个新数组，该数组的旧数组大小加 1，并将旧数组中的所有元素复制到新数组中，然后添加新数据。文本建议此方法的时间复杂度为 0(N^2)。我不确定如何？我认为时间复杂度是 O(N)，因为您正在为每个新元素创建一个新数组，您可以在其中拥有 N 个新元素，并且您正在复制再次近似为 N 的旧元素。因此我认为复杂度是O(N).
动态数组方法 2
第二种方法建议我们可以通过每次数组满时将数组的容量加倍来降低时间复杂度。例如，如果我们有一个初始容量大小为 4 的数组，并且我们将其填满，那么在尝试添加新数据时，我们将创建一个大小为 8 的新数组，并将所有旧元素复制到这个新数组中，然后添加新数据。
文中进一步指出此方法的时间复杂度为 O(N)。
有人可以澄清一下该方法的时间复杂度也是 O(N) 吗？
如果数组元素存储位置已经存在于内存中，则时间仅为内存写入时间。
当它不存在时，需要为数组分配更多的内存。
增加的时间因素是例程中用于读取现有数组、附加新元素然后将数组写回内存与仅将新元素写入现有内存位置的指令周期数。使用描述的重新分配方法执行此操作的次数越少。
如果存储的每个数组元素大小相同，则公式会很简单。
想象一下，从一个数组开始，其中 space 表示 1 个项目，然后我们继续追加 N 个项目，一次追加 1 个。第一次我们必须将 1 项复制到较大的 space，第二次复制 2 项，依此类推。在添加第 N 个项目之前，我们需要复制 N-1 个现有项目，所以总的来说我们已经完成了
1 + 2 + 3 + ... N-1 = N(N-1)/2
复制，所以这是 O(N^2)
使用第二种方法，我们复制的频率要低得多：第一个和第二个副本在我们添加这些项目时发生，但是下一个副本不会发生，直到大小为 4 的缓冲区已满，而之后的一个在大小 8 缓冲区已满。
如果 k 满足 2^(k-1) < N <= 2^k 那么我们会做
1 + 2 + 4 + 8 + ... 2^(k-1) = 2^k - 1
份数，即这是 O(N)
正在计算基于动态的数组的时间复杂度。
在我正在阅读的文本中，它提到了两种动态增加数组的方法。
动态数组方法 1
第一种方法指出，您可以构造一个大小为 1 的数组，并在每次将新数据推送到该数组时动态增加它。例如，如果您推送新数据，那么您将创建一个新数组，该数组的旧数组大小加 1，并将旧数组中的所有元素复制到新数组中，然后添加新数据。文本建议此方法的时间复杂度为 0(N^2)。我不确定如何？我认为时间复杂度是 O(N)，因为您正在为每个新元素创建一个新数组，您可以在其中拥有 N 个新元素，并且您正在复制再次近似为 N 的旧元素。因此我认为复杂度是O(N).
动态数组方法 2
第二种方法建议我们可以通过每次数组满时将数组的容量加倍来降低时间复杂度。例如，如果我们有一个初始容量大小为 4 的数组，并且我们将其填满，那么在尝试添加新数据时，我们将创建一个大小为 8 的新数组，并将所有旧元素复制到这个新数组中，然后添加新数据。
文中进一步指出此方法的时间复杂度为 O(N)。
有人可以澄清一下该方法的时间复杂度也是 O(N) 吗？
如果数组元素存储位置已经存在于内存中，则时间仅为内存写入时间。
当它不存在时，需要为数组分配更多的内存。
增加的时间因素是例程中用于读取现有数组、附加新元素然后将数组写回内存与仅将新元素写入现有内存位置的指令周期数。使用描述的重新分配方法执行此操作的次数越少。
如果存储的每个数组元素大小相同，则公式会很简单。
想象一下，从一个数组开始，其中 space 表示 1 个项目，然后我们继续追加 N 个项目，一次追加 1 个。第一次我们必须将 1 项复制到较大的 space，第二次复制 2 项，依此类推。在添加第 N 个项目之前，我们需要复制 N-1 个现有项目，所以总的来说我们已经完成了
1 + 2 + 3 + ... N-1 = N(N-1)/2
复制，所以这是 O(N^2)
使用第二种方法，我们复制的频率要低得多：第一个和第二个副本在我们添加这些项目时发生，但是下一个副本不会发生，直到大小为 4 的缓冲区已满，而之后的一个在大小 8 缓冲区已满。
如果 k 满足 2^(k-1) < N <= 2^k 那么我们会做
1 + 2 + 4 + 8 + ... 2^(k-1) = 2^k - 1
份数，即这是 O(N)