这个最长回文函数的空间复杂度是多少？

Question

function longestPalindromicSubstring(str) {
    let longest = '';
    for ( let i = 0; i < str.length; i++) {
         let word1 = palindromeFinder(str, i, i );
         let word2 = palindromeFinder(str, i, i+1);
         longest = [ word1, word2, longest ].reduce( (long, word) => long.length > word.length ? long : word)
    }
    return longest;
}

function palindromeFinder(str, left, right) {
    while ( left >= 0 && right < str.length && str[left] === str[right] ) {
        left--;
        right++;
    }
    return str.slice(left + 1, right)
} 

我非常确定时间复杂度是O(n^2)，因为主for循环乘以helper函数中的循环。在for循环中，我使用了reduce函数，但它只对输入string...am中的每个元素执行2-3次操作。我认为O(n^2)是错误的

我的主要问题是:这个函数的空间复杂度是O(1)吗

我最多只能存储3个变量longest, word1, word2，所以它是常量，对吧？

Answer 1

是什么导致了空间复杂性？

1. Variable
2. Data Structures
3. Function Call
4. Allocations

这些东西占用了空间，当涉及到时间和空间复杂性时，考虑了最坏的情况，忽略了固定时间(O(1))。

然而，你的函数有变量赋值，新的数据结构，函数调用，这使得空间复杂度为O(n)，而且，数组的每一项都消耗了额外的空间。

Answer 2

这个函数的空间复杂度是O(n)，因为您存储的数据结构的数量是固定的，每个结构取决于str，word1，word2，。O(1)实际上意味着常量，这肯定不是这样的