Это проблема 9.5 из интервью Cracking the Coding 5го издание

Эта проблема: Напишите метод для вычисления всех перестановок строки

Вот мое решение, написанное на Java (протестируйте, оно работает :))

public static void generatePerm(String s) {
    Queue<Character> poss = new LinkedList<Character>();
    int len = s.length();
    for(int count=0;count<len;count++)
        poss.add(s.charAt(count));
    generateRecurse(poss, len, "");
}
private static void generateRecurse(Queue<Character> possibles, int n, String word) {
    if(n==0)
        System.out.println(word);
    else {
        for(int count=0;count<n;count++) {
            char first = possibles.remove();
            generateRecurse(possibles, n-1, word+first);
            possibles.add(first);
        }
    }
}

Я согласился с автором, что мое решение работает вНа!) временная сложность, потому что для решения этой проблемы вы должны рассмотреть факториалы, например, для слова типа "top", есть три варианта для первой буквы, 2 для второй и так далее ....

Однако она не упомянула о сложности космоса. Я знаю, что интервьюеры любят спрашивать вас о временной и пространственной сложности вашего решения. Какова будет космическая сложность этого решения?

Моё первоначальное предположение было O (n2) потому что есть n рекурсивных вызовов на каждом уровне n. Таким образом, вы должны добавить n + n - 1 + n -, 2 + n - 3 ..... + 1, чтобы получитьп (п + 1)⁄2 который находится в O (n2). Я пришел к выводу, что существует n рекурсивных вызовов, потому что вы должны возвращаться n раз на каждом уровне, а сложность пространства - это количество рекурсивных вызовов, которые выполняет ваш алгоритм. Например, при рассмотрении всех перестановок «TOP», на уровне 3 рекурсивных вызова, gR ([O, P], 2, «T»), gR ([P, T], 2, «O»), gR ([T, O], 2, «P»). Является ли мой анализ сложности пространства правильным?