`追加`复杂性

Question

这个循环在 Go 编程语言中的计算复杂度是多少？

var a []int

for i := 0 ; i < n ; i++ {

  a = append(a, i)

}

并append以线性时间（重新分配内存和每个追加拷贝的一切），或在固定的时间里操作（比如在许多语言方式矢量类是implemnted）？

Answer 1

它不会在每个附加上重新分配，并且在文档中非常明确地说明：如果 s 的容量不足以容纳附加值，则 append 分配一个新的、足够大的切片，以适合现有切片元素和附加值。因此，返回的切片可能引用不同的底层数组。因此，摊销的常数时间是所询问的复杂性。