存储字符串的空间复杂度 O(1)

Question

我对空间复杂度有点困惑。这是 O(1) 空间复杂度还是 O(N) 复杂度？由于我正在创建一个大小为 n 的字符串，所以我的猜测是空间复杂度是 O(N)，这是正确的吗？

## this function takes in a string and returns the string

def test(stringval):
stringval2 = ""   
for x in stringval:
   stringval2 = stringval2 + x
return stringval2

test("hello")}

Answer 1

对，那是正确的。存储长度为 n 的新字符串的空间复杂度为 θ(n)，因为每个单独的字符都必须存储在某处。原则上，您可以通过注意到stringval2最终是副本stringval1并可能使用写时复制或其他优化来减少空间使用，但在这种情况下，没有理由怀疑情况确实如此。

希望这可以帮助！