Какова пространственная сложность этого алгоритма?

Question

Это проблема 9.6 из интервью Cracking the Coding (5-^е издание)

Реализуйте алгоритм для печати всех допустимых комбинаций n-пар скобок
ПРИМЕР
Вход: 3
Выход:"((())), (()()), (())(), ()(()), ()()()"

Вот алгоритм, который я реализовал (на Java)

private static Set<String> getAllComb(int n) {
      Set<String> allPoss = new HashSet<String>();
      if(n>0) {
          if(n==1) {
              allPoss.add("()");
          } else {
              Set<String> before = getAllComb(n-1);
              for(String phrase: before) {
                  int length = phrase.length();
                  for(int start = length - 2; start>=0; start--) {
                      if(phrase.charAt(start) == '(') {
                          String phraseToConsider = phrase.substring(0, start+1) + "()" +
                               phrase.substring(start + 1);
                          if(!allPoss.contains(phraseToConsider)){
                              allPoss.add(phraseToConsider);
                          }
                      }
                  }
                  String phraseToConsider = "()" + phrase.substring(0);
                  if(!allPoss.contains(phraseToConsider)){
                      allPoss.add(phraseToConsider);
                  }
              }
          }
      }
      return allPoss;
}

Это производит правильный вывод. Я знаю, что интервьюеры (по крайней мере, в Amazon) любят спрашивать вас о сложности вашего решения во времени и пространстве. Для сложности времени я смог показать, что алгоритм работает в O (n) с рекуррентным соотношением. У меня проблемы с анализом сложности пространства. Это рекурсивное решение, поэтому оно должно быть не менее O (n). Но при каждом рекурсивном вызове я также генерирую множество, ограниченное n. Будет ли общее пространство O (n) из-за n рекурсивных вызовов или O (n²) из-за установленного размера границы n для каждого рекурсивного вызова n?

Answer 1

Для сложности времени я смог показать, что алгоритм работает в O(n) с рекуррентным соотношением

Это не верно. Число последовательностей сбалансированных скобок задается каталонскими числами: таких последовательностей экспоненциально много. Ваш алгоритм не может быть линейным, если он также правильно решает проблему, потому что просто вывод экспоненциального числа решений сам по себе занимает экспоненциальное время.

Что касается сложности памяти, вы, кажется, храните все решения для n - 1 на каждом шагу n вашей рекурсии, поэтому сложность памяти также выглядит экспоненциально для меня, плюс другие строки, которые вы создаете, и рекурсивные вызовы, которые вы делаете на каждом шаге, что может только добавить к сложности.

Вы можете решить проблему, не используя экспоненциальную память: подумайте, как избавиться от сохранения всех предыдущих последовательностей.

Answer 2

Число способов записи n пар правильно подобранных скобок - это n- е каталонское число, которое на самом деле растет в геометрической прогрессии, а не в квадратичной. Пространственная сложность выходных данных равна O(2^n); см. статью в Википедии для быстрого обзора каталонских номеров.

Обратите внимание, что вы делаете не один рекурсивный вызов на каждой глубине, а потенциально O(n) рекурсивных вызовов.