时间递归算法的复杂性

Question

每当我看到一个递归解决方案，或者我为一个问题编写递归代码时，我很难弄清楚时间复杂度，在大多数情况下，我只是说它的指数？它是如何实际指数？人们怎么说它是2^n，什么时候是n！，什么时候是n^n或n^k。

我心中有一个疑问 -

1. 让的说找到一个字符串的所有排列
2. 找到一个数组到k其总结（指数所有序列，如何（O（N）！）我的确切计算）。
3. 找到总和为0的k大小的所有子集（k会出现在复杂性的某处，它应该是正确的？）。

可以any1帮助我如何计算这些问题的确切复杂性，我能够为他们编写代码，但它很难理解确切的时间复杂性。

Answer 1

找到所有在数组中总和为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)时间） 。

查找所有总和为0的k大小的子集（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)!) 

Answer 2

看看Master Theorem。这在教授完全解释。 Tim Roughgarden的Algorithms: Design and Analysis: Part I，来自斯坦福大学。这是我推荐的在线课程，但您可以在没有注册课程的情况下观看视频。如果您有兴趣，还有本课程的第二部分。