询问下述寻找最长回文子串的Python算法的时间复杂度

让咱们一步步拆解这段代码的执行逻辑，来算出它的时间复杂度：

1. 先看辅助函数is_palindrome #

这个函数用s == s[::-1]来判断回文：

• 切片s[::-1]会生成一个反转后的新字符串，这个操作的时间是O(k)，k是传入子串的长度
• 两个字符串的相等比较也需要遍历每个字符，同样是O(k)
• 所以整个is_palindrome函数的时间复杂度是O(k)，k为当前判断的子串长度

2. 主函数longestp的执行流程 #

外层循环 #

主函数里的for i in range(len(s)-1)循环会执行O(n)次，这里的n是原字符串s的总长度。

内层while循环 #

对于每个i，while循环会尝试从当前位置向左右扩展，寻找更长的回文。最坏情况（比如字符串是全相同字符，像"aaaaa"）下，这个while循环会遍历几乎整个字符串，也就是O(n)次迭代。

最关键的开销：每次迭代的回文判断 #

在while循环的每一次迭代中，都会调用is_palindrome，而每次判断的子串长度最多能达到n。比如全相同字符的场景，每次扩展后的子串长度都会增加，每次判断的时间是O(k)，k从当前最长回文的长度一直增长到n。把这些开销加起来，单个i对应的总开销是O(n²)（因为1+2+...+n的和是O(n²)量级）。

3. 整体时间复杂度 #

把外层循环的O(n)和内层的O(n²)开销相乘，这段算法的最坏时间复杂度是O(n³)。

当然也有最好情况：如果原字符串本身就是回文，函数会直接返回，这时候只调用了一次is_palindrome，时间复杂度是O(n)。不过算法复杂度通常讨论的是最坏情况的上限。

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