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

Question

我已经使用这个算法解决了这个问题，并且计算出递归调用的总数是n/2，因为我们总是传递原始字符串中少2个字符的子字符串。 slice() 函数的运行时复杂度为 O(n)。如果有 n/2 个函数调用，并且在每个函数调用中我们调用切片函数需要 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

I have solved the problem using this algorithm and have calculated that the total number of recursive calls is n/2 since we always pass a substring of the original string with 2 less characters. The runtime complexity of the slice() function is O(n). If there are n/2 function calls and in each one we call the slice function taking O(n) time, wouldn't the time complexity of this algorithm be O(n/2 * n) or O(n^2)?

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

I ran the code through chatGPT and it said the Big O notation for this is O(n)

这告诉您，您最好不要就作业问题咨询 ChatGPT。这次它只是让你感到困惑，但如果你自己得出了错误的结论，那么它可能会证实你的错误答案。 ChatGPT 经过训练，可以生成正确形式的响应，但它并不是特别擅长获得正确的答案，尤其是对于依赖细节的问题。

---

来自 ChatGPT 本身:

你

How reliable are ChatGPT's answers?

聊天GPT

As an AI Language Model, I strive to provide the most accurate and relevant information to the best of my abilities. However, ChatGPT's answers may not always be 100% accurate or appropriate for every situation or person. It is essential to consider the sources of the information I provide and use your judgment when making decisions based on my responses. In critical situations or cases where accuracy is crucial, it is best to consult with a qualified expert in the particular field.