string - 空间复杂度 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 的副本并可能使用写时复制或其他优化，但在这种情况下，没有理由怀疑是这种情况。

希望这可以帮助!