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

Question

Это проблема 9.6 из Крекинг Кодирование интервью (5 ^й издание)

реализовать алгоритм, чтобы напечатать все допустимые комбинации п-пар скобок
Пример
Входной сигнал: 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) с рекуррентным соотношением. У меня возникают проблемы с анализом сложности пространства. I это рекурсивное решение, поэтому должно быть не менее O (n) Но при каждом рекурсивном вызове я также генерирую множество, ограниченное n. Будет ли общее пространство O (n) из-за n рекурсивных вызовов или оно O (n) из-за установленного размера связанного n для каждого рекурсивного вызова n?

Answer 1

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

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

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

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

Answer 2

Числа способов, чтобы написать п пара надлежащим образом подобранных скобок является п го Каталонского числа, которое на самом деле растет экспоненциально, а не quadratical. Только пространственная сложность выхода равна O (2^n); см. the wikipedia article для краткого обзора каталонских номеров.

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