Python回文字符串检测的Big O复杂度疑问

经典回文检测有两种常见解法：

• 反转字符串后与原串对比
• 对比首尾字符后递归处理内部子串

一、反转字符串方案的时间复杂度与底层实现疑问 #

问题：调用string[::-1]的时间复杂度是O(n)还是O(n²)？已知字符串追加字符是O(n)操作（列表追加为O(1)），想知道执行reversedString = string[::-1]时，Python是将string视为字符串还是数组？

解答：

• 时间复杂度：string[::-1]的时间复杂度是O(n)。Python的字符串切片反转是一次性复制原字符串的所有字符到新内存空间，不会像逐字符追加那样产生多次O(n)的拷贝，因此整体是线性时间。
• 底层处理：Python中的字符串是不可变序列，内部采用连续内存存储字符（类似数组的实现），切片操作会直接基于原串的内存结构逆序复制字符，不会因为字符串不可变而额外增加开销。

二、递归方案的空间复杂度疑问 #

给出的递归实现代码：

def check_palindrome(string):
    if len(string) <= 1:
        return True
    return (string[0] == string[-1]) and check_palindrome(string[1:-1])

问题：该实现的空间复杂度是O(n)还是O(n²)？已知递归调用会占用O(n)栈空间，但考虑到每个栈帧都会存储字符串，是否会导致空间复杂度为O(n²)？

解答：

• 空间复杂度是O(n²)，原因如下：
  1. 递归深度为O(n)：最坏情况下（比如全相同字符的字符串），递归会执行n/2次，对应O(n)层栈帧。
  2. 子串的额外空间开销：Python字符串不可变，每次string[1:-1]切片都会生成一个新的字符串对象，长度比原串少2。所有栈帧中存储的字符串总长度为n + (n-2) + (n-4) + ... + 1，约等于n²/2，属于平方级的空间开销。
  3. 优化方案：如果要将空间复杂度降到O(n)，可以修改递归逻辑，不传递子串而是传递首尾索引，每个栈帧仅存储两个整数。优化后的示例代码：

def check_palindrome(string, left=0, right=None):
    if right is None:
        right = len(string) - 1
    if left >= right:
        return True
    return (string[left] == string[right]) and check_palindrome(string, left+1, right-1)

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