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中文網其他相關文章！