动态数组放置元素的时间复杂度 [英] dynamic array's time complexity of putting an element
问题描述
在笔试中，我遇到这样的问题:
In a written examination, I meet a question like this:
当动态数组已满时，它将扩展到两倍的空间，就像2到4、16到32等.但是将元素放入数组的时间复杂度是多少?
When a Dynamic Array is full, it will extend to double space, it's just like 2 to 4, 16 to 32 etc. But what's time complexity of putting an element to the array?
我认为不应该考虑扩展空间，因此我写了O(n)，但不确定.
I think that extending space should not be considered, so I wrote O(n), but I am not sure.
答案是什么?
推荐答案
这取决于所提出的问题.
It depends on the question that was asked.
如果问题要求插入一次所需的时间，则答案为O(n)，因为big-O表示最坏的情况".在最坏的情况下，您需要扩展阵列.增长数组需要分配一个更大的内存块(通常说来是2倍，但其他因素可能大于1)，然后复制整个内容，即n个现有元素.在某些语言(例如Java)中，还必须初始化额外的空间.
If the question asked for the time required for one insertion, then the answer is O(n) because big-O implies "worst case." In the worst case, you need to grow the array. Growing an array requires allocating a bigger memory block (as you say often 2 times as big, but other factors bigger than 1 may be used) and then copying the entire contents, which is the n existing elements. In some languages like Java, the extra space must also be initialized.
如果问题要求摊销时间，则答案为O(1).另一种说法是，n相加的成本为O(n).
If the question asked for amortized time, then the answer is O(1). Another way of saying this is that the cost of n adds is O(n).
怎么可能?每个加法为O(n)，但其中的n个也需要O(n).这就是摊销之美.为简单起见，假设数组以大小1开头，每次填充时以2的倍数增长，所以我们总是复制2个元素的幂.这意味着第一次生长的成本为1，第二次为2，以此类推.通常，生长到n个元素的总成本为TC = 1 + 2 + 4 + ... n.好吧，不难发现TC = 2n-1.例如.如果n = 8，则TC = 1 + 2 + 4 + 8 = 15 = 2 * 8-1.因此，TC
How can this be? Each addition is O(n), but n of them also require O(n). This is the beauty of amortization. For simplicity, say the array starts with size 1 and grows by a factor of 2 every time it fills, so we're always copying a power of 2 elements. This means the cost of growing is 1 the first time, 2 the second time, etc. In general, the total cost of growing to n elements is TC=1+2+4+...n. Well, it's not hard to see that TC = 2n-1. E.g. if n = 8, then TC=1+2+4+8=15=2*8-1. So TC is proportional to n or O(n).
无论初始数组大小或增长因子如何，只要该因子大于1，此分析均有效.
This analysis works no matter the initial array size or the factor of growth, so long as the factor is greater than 1.
如果您的老师很好，他或她会模棱两可地问这个问题，看看您是否可以讨论两个答案.
If your teacher is good, he or she asked this question in an ambiguous manner to see if you could discuss both answers.
这篇关于动态数组放置元素的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
