Если единственным входом является строка и создается дополнительная строка, является ли сложность пространства функцией O (n)?

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) пространственной сложностью ?

Answer 1

Да. Вы правы. Код, который вы показали, имеет сложность пространства O(s.size()).

Возможно, вызовы функций к longestPalStartingAtIndex также будут копировать s и потребовать места, но в итоге мы говорим о O(some_constant * s.size()), поэтому это все еще O(s.size()).