Python中使用扩展切片反转字符串的空间复杂度是多少？

结论很明确：Python中常规的字符串反转操作空间复杂度是O(n)，n为原字符串的长度。

原因在于Python的字符串是不可变类型——你没法直接修改原字符串的任何字符，所有看似“修改”字符串的操作，本质都是创建一个全新的字符串对象来存储结果。反转操作自然也不例外：不管是用切片s[::-1]，还是通过''.join(reversed(s))实现反转，最终都会生成一个和原字符串长度相同的新字符串，这部分需要占用O(n)的额外空间。

至于有些网站声称空间复杂度是O(1)，大概率是混淆了其他编程语言的情况——比如在C++中，字符数组是可变的，可以在原数组上原地反转，不需要额外开辟和原数组等长的空间，这时空间复杂度才是O(1)。还有一种可能是部分分析把输入本身占用的空间排除，只计算辅助变量的空间，但严格来说，反转操作生成的新字符串属于额外空间开销，不能忽略。

内容的提问来源于stack exchange，提问作者Lindy T