如果唯一的输入是一个字符串，又创建了一个额外的字符串，那么函数复杂度是O(n)space吗？

Question

例如：

    string longestPalStartingAtIndex(string s, int index) {
        int i = index - 1; 
        int j = index + 1;
        
        while (j < s.size() && s.at(index) == s.at(j)) j++;
        
        while (i >= 0 && j < s.size()) {
            if (s.at(i) == s.at(j)) {
                i--; j++;
            }
            else {break;}
        }

        return s.substr(i + 1, (j - 1) - (i + 1) + 1);
        
    }

    string longestPalindrome(string s) {
        
        string longest; string temp;
        for (int i = 0; i < s.size(); i++) {
            temp = longestPalStartingAtIndex(s, i);
            if (longest.size() < temp.size()) longest = temp;
        }
        return longest;
        
    }

在 longestPalindrome 中，因为 n 是 string s 或者它的长度，正在创建一个额外的字符串（用于存储 s 的一些子字符串）来实现函数O(n) space 复杂度？

Answer 1

是的。你是对的。您显示的代码具有 O(s.size()) space 的复杂性。

可以说对 longestPalStartingAtIndex 的函数调用也会复制 s 并需要 space，但最后我们谈论的是 O(some_constant * s.size()) 所以它仍然是 O(s.size()).

如果唯一的输入是一个字符串，又创建了一个额外的字符串，那么函数复杂度是O(n)space吗？

If the only input is a String and an additional String is created, is the function O(n) space complexity?

c++

algorithm

big-o

time-complexity