Python回文判断代码时间复杂度为何是O(n²)？若错误实际是多少？

认为时间复杂度为O(n²)的原因 #

这个说法是基于Python早期版本（2.4及更早）的字符串实现逻辑来的：

• Python中字符串属于不可变对象，早期版本没有对字符串追加操作做特殊优化，每次执行reversedString += str[i]的时候，都需要重新申请一块长度为当前reversedString长度+1的新内存，把旧字符串的所有字符和新字符一起复制到新内存中。
• 整个循环要执行n次（n为输入字符串长度），每次复制的字符数从1递增到n，总操作次数是n(n+1)/2，所以会得出O(n²)的时间复杂度结论。

实际运行的时间复杂度 #

这个说法现在已经不成立，当前主流Python版本（2.5及之后）跑这段代码的时间复杂度为O(n)：

• 新版本Python对字符串的+=操作做了专属优化：只要解释器检测到目标字符串变量没有其他地方引用，就会直接在原内存空间上动态扩容，不需要每次都复制整个旧字符串，单次追加操作的均摊时间复杂度降到了O(1)，整个循环的总时间复杂度为O(n)。
• 最后一步字符串相等判断需要逐个比对两个长度为n的字符串，时间复杂度也是O(n)，所以整体的时间复杂度还是线性的O(n)。

def isPalindrome(str):
    reversedString = ''
    for i in range(len(str)-1,-1,-1):
        reversedString += str[i]
    return str == reversedString

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