資料結構與演算法
某個可變長度陣列在容量已滿時加入元素，會重新配置2倍容量的區域並複製所有元素。對容量為1的空陣列逐一加入1,000個元素時，被複製的元素總數為多少？
- A10
- B1,023
- C499,500
查看答案與解析
正確答案：B. 1,023
容量每次滿了就以1、2、4、…、512的方式變為2倍，每次都要複製當時的所有元素，因此複製總數為 1 + 2 + 4 + … + 512 = 1,023。對1,000次加入而言，複製約為元素數的1倍，因此每次加入的工作量平均為固定值，也就是攤銷 O(1)。若容量每次只增加1，複製為 1 + 2 + … + 999 = 499,500，是 O(n²)。10是重新配置區域的次數，不是被複製的元素數。
- A. 這是重新配置區域的次數（1→2→…→1024共10次），不是被複製的元素數。
- B. 正確。1 + 2 + 4 + … + 512 = 1,023，每次加入平均約複製1次。
- C. 這是容量每次只增加1時的複製總數。