递归检查字符串是否为回文的算法的时间复杂度是多少？

Question

我已经使用这个算法解决了这个问题，并计算出递归调用的总数是 n/2，因为我们总是传递原始字符串的少 2 个字符的子字符串。 slice() 函数的运行时复杂度为 O(n)。如果有 n/2 个函数调用，并且在每个函数调用中我们调用 slice 函数花费 O(n) 时间，那么这个算法的时间复杂度不是 O(n/2 * n) 或 O(n^2) 吗？

function checkIfPalindrome(string) {
  const leftMost = string[0],
    rightMost = string[string.length - 1];
  //base case 1: if length of original string is an odd number, then this base case applies
  if (string.length === 1) return true;

  //base case 2: if length of original string is an even number, then this base case applies
  if (string.length === 2) {
    if (leftMost === rightMost) return true;
    else return false;
  }

  //check if leftmost char === rightmost character
  //if true, continue recursive process, else return false;
  if (leftMost !== rightMost) return false;

  return checkIfPalindrome(string.slice(1, string.length - 1));
}

我通过 chatGPT 运行代码，它说这个的大 O 符号是

O(n)

，但我对此持保留态度。

Answer 1

我已经使用这个算法解决了这个问题，并计算出递归调用的总数是 n/2，因为我们总是传递原始字符串的少 2 个字符的子字符串。 slice() 函数的运行时复杂度为 O(n)。如果有 n/2 个函数调用，并且在每个函数调用中我们调用 slice 函数花费 O(n) 时间，那么这个算法的时间复杂度不是 O(n/2 * n) 或 O(n^2) 吗？

是的，你的推理和结论是正确的。时间复杂度为 O(n²) = O(n²/2) = O(n/2 * n)。第一个是常规表达方式，可能是您的评分者更喜欢的表达方式，但在技术上都是正确的。

我通过 chatGPT 运行代码，它说这个的大 O 表示法是 O(n)

这告诉你，你最好不要在作业问题上咨询 ChatGPT。这次它只是让你感到困惑，但如果你自己得出了错误的结论，那么它可能会肯定你的错误答案。 ChatGPT 经过训练可以生成大致正确形式的回复，但它并不是特别擅长获得正确的答案，尤其是对于取决于细节的问题。

---

来自 ChatGPT 本身：

你

ChatGPT 的答案有多可靠？

聊天GPT

作为人工智能语言模型，我力求尽我所能提供最准确和最相关的信息。但是，ChatGPT 的答案可能并不总是 100% 准确或适合每种情况或每个人。在根据我的回答做出决定时，请务必考虑我提供的信息来源并使用您的判断。在关键情况下或准确性至关重要的情况下，最好咨询特定领域的合格专家。