再帰的な解決策を見たり、問題に対して再帰的なコードを書いたりするときはいつでも、時間の複雑さを理解するのは本当に難しいです. 実際にはどのように指数関数的ですか？n! のときは 2^n、n^n または n^k のときはどのように言いますか。
いくつか質問があります -
そのような質問の正確な複雑さを計算する方法を教えてください。コードを書くことはできますが、正確な時間の複雑さを理解するのは難しいです。
配列内で合計 k になるすべてのシーケンスを見つけます (指数、正確に計算するにはどうすればよいですか)。
F(a, n, k)のすべての部分集合の数S ⊂ {0, 1, ..., n-1}を
∑ a[i] == k
i∈S
F(array, length of array, k)次に、問題を 2 つのサブ問題に分割することにより、再帰的に計算できます( の場合n > 0)。
のサブセットは{0, 1, ..., n-1}、含むクラスと含まないクラスの 2 つのクラスに分割できますn-1。
再帰を取得します
F(a,n,k) = F(a,n-1,k) + F(a,n-1, k-a[n-1])
T(n)を計算に必要な時間とします (下線は、配列やより高速なアルゴリズムではなく、のみに依存するF(_,n,_)ことを示します)。 then の再帰は、すぐに意味します。T(n)nkkF
T(n) = 2 * T(n-1)
のためにn > 0。
の場合n == 0、定数時間で解を計算できます。
F(a, 0, k) = k == 0 ? 1 : 0
だから私たちはT(n) = 2^n * T(0)帰納的に持っています。
サブセットをカウントするだけでなく出力する場合、複雑さが増しO(n * 2^n)、その境界はタイトになります (すべて0の の配列の場合、 with k == 0、すべてのサブセットが条件を満たし、それらを出力するのにΘ(n * 2^n)時間がかかります)。
合計が 0 であるサイズ k のすべてのサブセットを見つけます (k は複雑さのどこかに来るでしょうか?それは正しいはずですか?)。
はい、その問題の複雑さは と に依存しnますk。
とするカーディナリティのF(a,n,k,s)サブセットのS ⊂ {0, 1, ..., n-1}数k
∑ a[i] == s
i∈S
についてk == 0は、再び定数時間の答えが得られます。 の場合、そのようなサブセット (空のセット) が 1 つあり、それ以外の場合s == 0はありません。k > nセット{0, 1, ..., n-1}にはカーディナリティのサブセットがないためk、F(a,n,k,s) = 0if k > n.
の場合、上記のように、含むサブセットと含まない0 < k <= nサブセットを別々に考えることができます。n-1
F(a,n,k,s) = F(a,n-1,k,s) + F(a,n-1,k-1,s - a[n-1])
そして、私たちが見つけた時間の複雑さについて
T(n,k) = T(n-1,k) + T(n-1,k-1)
その再帰は二項係数からわかり、
T(n,k) = n `choose` k = n! / (k! * (n-k)!)
（付きT(n,0) = 1）。
繰り返しになりますが、セットをカウントするだけでなく出力する場合、時間の複雑さが増します。ここでは、すべてのセットにカーディナリティがあるため、次kのようになります。
k * n! / (k! * (n-k)!)
マスター定理を見てください。それは教授で完全に説明されています。Tim Roughgarden's Algorithms: Design and Analysis: Part I、スタンフォードから。オススメのオンライン授業ですが、入会しなくても動画は見られます。興味があれば、このコースのパート II もあります。