algorithm - 私の教授は、このアルゴリズム分析で再帰的なケースをどのように思いつきますか?

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})。

したがって、再帰するときは、 に 1 つの要素を追加しP、 から 1 つの要素を削除しますS。

したがってm、1 ずつ増加し、1 ずつn減少します。したがって、次のようになります。T(m+1, n-1)

それが役立つことを願っています。