为什么这段代码在Go O（n²）中而不是O（n）中？

Question

我正在阅读《有效的Go》，其中有一段代码我觉得很O(n)复杂，但确实如此O(n²)。为什么将此for range循环视为O(n²)？

可以在这里找到（在#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)。