每当我看到递归解决方案，或者我为一个问题编写递归代码时，我真的很难弄清楚时间复杂度，在大多数情况下我只是说它的指数？它实际上是如何指数级的？人们怎么说它是2^n，当它是n！时，当它是n^n或n^k时。
我心里有一些疑问——
- 假设找到字符串的所有排列(O(n！))
- 找到数组中总和为 k 的所有序列(指数，我如何精确计算)。
- 找到所有大小为 k 且总和为 0 的子集(k 会不会在复杂度的某个地方出现，它应该是正确的？
any1 可以帮助我如何计算此类问题的确切复杂度，我能够为它们编写代码，但很难理解确切的时间复杂度。
找到数组中总和为 k 的所有序列(指数，我如何精确计算)。
设F(a, n, k)是S ⊂ {0, 1, ..., n-1}的所有子集的数量，以便
∑ a[i] == k
i∈S
然后我们可以通过将问题拆分为两个子问题(对于n > 0)来递归计算F(array, length of array, k)。
{0, 1, ..., n-1}的子集可以分为两个类，一个包含n-1，一个不包含
。我们获得递归
F(a,n,k) = F(a,n-1,k) + F(a,n-1, k-a[n-1])
让我们T(n)计算F(_,n,_)所需的时间(下划线表示T(n)仅取决于n，而不依赖于数组或k[尽管对于特定的数组和k更快的算法是可能的]。然后F的递归立即暗示
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的数组，带有k == 0，所有子集都满足条件，打印它们需要Θ(n * 2^n)时间)。
找到所有大小为 k 且总和为 0 的子集(k 会不会在复杂度的某个地方出现，它应该是正确的？
是的，该问题的复杂性取决于n和k。
设F(a,n,k,s)基数S ⊂ {0, 1, ..., n-1}子集的数目k使得
∑ a[i] == s
i∈S
对于k == 0，我们再次有一个常量时间答案，如果s == 0，则有一个这样的子集(空集)，否则没有。对于k > n集合{0, 1, ..., n-1}没有基数k的子集，所以F(a,n,k,s) = 0如果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教授的《算法：设计与分析：第一部分》对此进行了完美的解释。这是我推荐的在线课程，但您无需注册课程即可观看视频。如果您有兴趣，本课程还有第二部分。