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

Question

我制作了一个使用 k-sub 算法的函数(从 n 个元素的集合中生成大小为 k 的所有子集)。我将对其进行 n 次迭代以创建所有大小的所有子集(即幂集)。

既然我已经有了生成幂集的方法，为什么还要使用这个函数呢？因为我希望在增加子集长度的情况下生成子集。

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 就在那里。但是 recurciveSelectSubset 函数的复杂度是多少？

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

这就是我计算 recursiveSelectSubset 复杂度的方法。要生成大小为 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。 ( here )

所以上述函数的总时间复杂度是 2^n。