Go 中'append”的时间复杂度是多少？

Go 中的追加复杂度

问题：

Go 中以下循环的计算复杂度是多少？

var a []int
for i := 0 ; i < n ; i++ {
  a = append(a, i)
}

append 是在线性时间内操作，还是在摊余常数中操作

答案：

Go 编程语言规范规定，如果需要，append 会执行重新分配：

If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large slice that fits both the existing slice elements and the additional values. Thus, the returned slice may refer to a different underlying array.

但是，具体算法必要时增长目标切片取决于实现。对于当前的gc编译器来说，该算法是摊销常数时间。

摊销常数时间说明：

切片容量以贪心方式增加：

• 如果旧容量大于旧容量的两倍，则新容量设置为旧容量容量。
• 否则，如果旧长度小于 1024，则新容量设置为旧容量的两倍。
• 否则，新容量增加四分之一，直到达到最小化旧容量的大小。

这种方法可确保重新分配所花费的总时间摊销为 O(n)，其中n 是结果切片的长度。

实现注意事项：

Go 语言规范允许不同的append 实现。例如，实现可能是慷慨的（分配超过最小必要量的）或简约的（分配最小必要量的）。 Go gc 编译器使用慷慨的动态数组摊销常数时间算法。

总结：

Go 中追加的复杂性取决于实现。然而，Go gc 编译器和 gccgo 等常见实现使用摊销常数时间算法。

以上是Go 中'append”的时间复杂度是多少？的详细内容。更多信息请关注PHP中文网其他相关文章！