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

我正在阅读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)复杂性。

最佳答案

每次连接str += fmt.Sprint(elem)时，都会创建一个新的String，该新的str必须将上一个n(n+1)/2的字符转移(复制)到新的O(n^2)中。在步骤1中，您复制1个字符，在步骤2、2中，依此类推。这将得到ojit_code副本。因此，复杂度为ojit_code。

关于go - 为什么这段代码在Go O(n²)中而不是O(n)中？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57163339/