go - 为什么这段代码在 Go 中是 O(n²) 而不是 O(n)？

Question

我正在阅读 Effective Go ，并且有一段代码我认为是 O(n) 复杂度，但它是 O(n²)。为什么这个 for range 循环被认为是 O(n²)？

找到here (under #interfaces)

type Sequence []int
...
func (s Sequence) String() string {
    ...
    for i, elem := range s { // Loop is O(N²); will fix that in next example.
        if i > 0 {
            str += " "
        }
        str += fmt.Sprint(elem)
    }
    ...
}

我认为它是 O(n) 的原因是因为 s 只有一次迭代，if 语句和 fmt.Sprint 的复杂度不应为 O(n)。

Answer 1

每次连接 str += fmt.Sprint(elem) 都会创建一个新的 String，它必须传输(复制)上一个 的字符str 进入新的。在第 1 步中，您复制 1 个字符，在第 2 步、第 2 步等中。这会产生 n(n+1)/2 个副本。因此，复杂度为 O(n^2)。