计算循环空间复杂度的基础是什么？ [关闭]

想象一下，您循环 n 次，并且每次迭代都会创建一个空间 n 的字符串，其范围仅在该迭代内（因此在下一次迭代中不再可访问）。我会说我使用 O(n^2) 空间，因为对于 n 次迭代，我使用 n 空间。

然而，从逻辑上讲，如果每个循环都销毁前一个迭代的字符串（n 空间）并用本次迭代的字符串（n 空间）覆盖它，那么在整个循环中，您将只使用 O(n) 空间。我很困惑是否要确认 O(n) 还是 O(n^2) 空间？

举个例子：

s = "hello"
for _ in range(len(s)):
    newString = s[:]
return newString

您只需测量任一时间所需的最大空间量。您的循环需要 O(n) 空间，因为正如您所说，任何时候只有一次迭代在范围内。

在没有显式释放内存的垃圾收集语言中，有理由相信您所使用的任何语言的实现，以确保您实际使用的空间量最多与您需要的空间量成正比，因此不会影响你的空间复杂度。

在大多数情况下，忽略诸如渐近空间复杂度分析的内存碎片之类的问题也是合理的，即使这样的问题can实际上改变了现实世界的渐近复杂性。