Как мой профессор придумал рекурсивный случай в этом анализе алгоритма?

Question

Мой профессор дал нам следующее объяснение рекурсивного алгоритма для нахождения перестановок набора чисел:

---

---

Когда у него есть (T(m+1), n-1)), откуда это? Почему это m + 1 и n-1? Я действительно не понимаю, откуда это.

Answer 1

Как он сказал, m представляет текущий размер P а также n представляет размер S, в каждом рекурсивном вызове вы удаляете номер из S и добавить его в PТаким образом, размер вашей текущей перестановки увеличивается на 1 (m+1) и количество доступных чисел для добавления к перестановке уменьшается на 1 (n-1)

Обратите внимание, что он умножается на n как вы выполняете это действие для каждого числа в S,

Answer 2

Обратите внимание на ту часть, которая говорит:

Позволять m быть длиной P а также n быть размером с S

А потом в printperm(P, S)звонишь printperm((P,i), S-{i}),

Итак, при повторении мы добавим один элемент к Pи удалить элемент из S,

таким образом m увеличится на один и n будет уменьшаться на единицу, таким образом, мы получаем T(m+1, n-1)

Надеюсь, это поможет.