在数组末尾插入n个元素的时间复杂度是多少？ [英] What is the time complexity of inserting n elements to the end of an array?

问题描述

我知道将元素插入数组需要花费恒定的时间，让我们说c。

i know that inserting an element to an array takes a constant time let us say c.

我尝试过的操作：

用于插入n个元素
time = c + c + c + ....... n times = nc

我想问问它是n或o（1）的大O。

i want to ask that will it be big O of n or o(1).

推荐答案

是的，添加 n 个元素需要O（n）时间，但是添加单个项目却不是O（1）。它被摊销 O（1）。

Yes, adding n elements requires O(n) time, but adding an individual item is not O(1). It's amortized O(1).

任何给定的加法都可能需要O（n）时间，因为当前数组的空间已被填充，因此必须将其复制到另一个更大的空间。

Any given add may require O(n) time by itself because the current array's space has been filled, so it must be copied to another, larger space.

但是，如果新空间分配的常量系数大于原始空间的（通常使用2），则复制成本将摊销因此，每次添加的平均时间如您所说是恒定的，而 n 添加的时间为O（n）。

But if the new space allocation is a constant factor greater than one of the original (2 is often used), then the copy costs amortize so that average time per add is constant as you say, and n adds are O(n).

To更清楚地说，考虑因子为2且初始数组大小为1的情况。然后考虑将数组的大小从大小1扩展到足以容纳的复制成本，对于任何k> = 0的元素都是2 ^ k + 1个元素。这个大小是2 ^（k + 1）。复制总成本将包括所有复制过程，这些复制过程将以2因子的步骤变大：

To make this clearer, consider the case where the factor is 2 and initial array size is 1. Then consider copy costs to grow the array from size 1 to where it's large enough to hold, 2^k+1 elements for any k>=0. This size is 2^(k+1). Total copy costs will include all the copying to become that big in factor-of-2 steps:

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

等式归因于基本代数。结果是O（n）。但是，最后一个副本本身具有n = 2 ^ k个元素，也为O（n）。

The equalities are due to basic algebra. The result is O(n). However, the last copy itself has n = 2^k elements, which is also O(n).

这篇关于在数组末尾插入n个元素的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！