每当我看到一个递归解决方案，或者我为一个问题编写递归代码时，我真的很难弄清楚时间复杂度，在大多数情况下我只是说它是指数级的？它实际上是如何指数化的？人们怎么说它是 2^n，当它是 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)通过将问题拆分为两个子问题（对于n > 0）来递归计算。
的子集{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)归纳。
如果不仅要计算子集，还要输出子集，那么复杂度就会变大，并且边界很紧（对于所有sO(n * 2^n)的数组，其中，所有子集都满足条件，并且打印它们需要时间）。0k == 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 的算法：设计与分析：第一部分，来自斯坦福。这是我推荐的在线课程，但您无需注册即可观看视频。如果您有兴趣，还有本课程的第二部分。