递归判断回文字符串算法的时间复杂度到底是多少？

你的分析是正确的，这个递归实现的回文字符串判断算法时间复杂度为O(n²)，ChatGPT给出的O(n)结论有误，具体分析如下：

核心原因拆解 #

• 递归调用次数：对于长度为n的字符串，递归调用次数为⌊n/2⌋次，属于O(n)级别的调用次数。
• slice()的开销：JavaScript中string.slice(start, end)会创建一个新的子字符串，新字符串的长度为end - start，因此该操作的时间复杂度与子字符串长度成正比，即每次递归中的slice操作开销为O(k)，其中k是当前处理的字符串长度。

总时间复杂度计算 #

把每次递归的slice开销累加起来：

• 当n为偶数时，总开销为：(n-2) + (n-4) + ... + 2 = n(n/2 - 1)/2 ≈ n²/4
• 当n为奇数时，总开销为：(n-2) + (n-4) + ... + 1 = ((n-1)/2)² ≈ n²/4

无论n是奇数还是偶数，总时间复杂度都属于**O(n²)**级别。

优化到O(n)的方案 #

如果要将时间复杂度优化到O(n)，可以避免每次递归截取字符串，改用左右指针传递索引的方式，这样没有字符串复制的开销：

function checkIfPalindrome(string, left = 0, right = string.length - 1) {
  // 基准情况：左右指针相遇或交叉，说明前面的字符都匹配
  if (left >= right) return true;
  // 两端字符不匹配，直接返回false
  if (string[left] !== string[right]) return false;
  // 递归检查内层子串
  return checkIfPalindrome(string, left + 1, right - 1);
}

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