基于k-sub算法的子集生成函数的时间复杂度计算.

Question

我做了一个使用 k-sub 算法的函数(从 n 个元素的集合中生成大小为 k 的所有子集)。 我正在迭代它 n 次以创建所有大小的所有子集(即 powerset)。

当我已经有生成电源组的方法时，为什么还要使用此功能？因为我希望子集的长度不断增加。

for(int k = 0; k <= n; k++){
recursiveSelectSubset(){
if(k == n){
for(int i = 0; i < n; i++){
subset[i] = true;               
}                
}
if(k == 0){
for(int i = 0; i < n; i++){
subset[i] = false;
}
}
if(k > 0 && k < n){
subset[n-1] = true;
recursiveSelectSubset(subset, n-1, k-1, isminimum, io);
subset[n-1] = false;
recursiveSelectSubset(subset, n-1, k, isminimum, io);
}                
}
}

现在，由于该函数被调用了n次，因此n就在那里。 但是递归选择子集函数的复杂性是什么？

我觉得那个函数的作用是生成大小 k 的所有子集，所以它就像 nCk. 具有复杂性 O(n^k)。现在它运行从 1 到 n 的所有可能值 k 我们可以说，这个片段的最终复杂度是 O(n^(n+1))

这就是我计算递归选择子集复杂性的方式。 要生成大小 k = 0 的所有子集，需要 N^0。要生成大小为 k = 1 的所有子集，需要 n^1。以这种方式生成大小 k = n 的子集，它将需要 n^n.并且总时间为 n^0 + n^1 + .... + n^n = n^(n+1)。

但这里再次怀疑，要生成大小 k = n 的子集，它应该需要恒定的时间，对吗？而不是 n^n。所以这样我的计算就错了。但根据 nCk，它可以取 n^n = n^0 = 1。那么如何对 k 的所有值求和呢？

那么什么是正确的复杂性呢？

附言如果我的分析是错误的，我想澄清一下，它是如何错误的？

Answer 1

经过一些冲浪和讨论，我找到了一个答案，我在这里发布以备将来帮助。

recursiveSelectSubset() 将计算 nCk 并花费时间 n^k。当 k = 0 到 n 时，正在调用此函数。

因此，它所花费的总时间是所有调用 recurseiveSelectSubset() 所花费的时间的总和。

n^0 + n^1 + n^2 + .... + n^n

这实际上是二项式系数的总和，它的总和为 2^n。

因此，上述函数的总时间复杂度为 2^n。