List和Iterator ADTs

Question

假设我们正在维护一个元素集合C，这样，每次向集合中添加一个新元素时，我们都会将C的内容复制到一个大小刚好合适的新数组列表中。在本例中，向初始空集合C添加n个元素的运行时间是多少？

Answer 1

• 第一个元素被添加。(1次手术)。
• 第二个元素被添加。复制第一个元素并添加新元素(2个操作)。
• 第三个元素被添加。复制第1和第2元素并添加新元素(3次操作)
• 添加了n_th元素。复制(_n-1)元素并添加新元素(n操作)。

因此，对于添加n个元素，我们共有一个1+2+3+...+n操作，等于 (n)(n+1)/2 = (n^2+n)/2。在大O符号中，可以说将元素添加到集合中是O(n^2)。