递归调用中Python字符串切片的时间与空间复杂度分析是否正确？

先看这段递归反转字符串的Python代码：

def reverse(s):
    if len(s) == 0:
        return s
    else:
        return reverse(s[1:]) + s[0]

你的分析完全正确，具体拆解如下：

• 每次递归里的s[1:]切片操作，会生成一个新字符串，长度是当前字符串长度减1，这个操作的时间和空间复杂度都是O(k)（k为当前字符串长度），第一次调用是O(n)，第二次O(n-1)，直到最后一次O(1)。
• 整个递归过程会触发n次调用，对应字符串的每个字符。
• 总时间复杂度：把每次切片的时间加起来，就是O(n) + O(n-1) + ... + O(1)，求和后等价于O(n²)。
• 总空间复杂度：切片生成的所有新字符串累计占用O(n²)空间，而递归调用栈的空间是O(n)，显然二次空间开销占主导，所以整体空间复杂度是O(n²)。

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