递归程序的时间复杂度以查找给定长度 (k) 的数组的所有子集

Question

我编写了一个程序来查找长度为 K 的数组的所有子集。我无法找到它的时间复杂度，因为递归调用在 for 循环中。

我认为这不是 theta，因为程序可以终止，所以我假设是大 O，但就时间复杂度而言 - 很难说。有什么想法或指导吗？谢谢！

myarr = [1,2,3]
k = 2
finalarr = []
def subsets(n, k):

    if k == len(n):
        if not n in finalarr:
            finalarr.append(n)
        return

    for i in n:
        aux = n[:]
        aux.remove(i)
        result = subsets(aux, k)

        if not result in finalarr and result:
            finalarr.append( result)

subsets(myarr, k)
print (finalarr)

Answer 1

找到给定长度 (k) 的数组的所有子集的最佳时间复杂度等于 2 的 k 次方。解释是考虑数组中的每个元素处于两种可能的状态：属于或不属于子集。棘手的事情是要记住空集。这是一个示例：https://www.mathsisfun.com/sets/images/power-set.svg

Answer 2

让我们用 N 表示原始集合，用 n 表示它的基数。

在对函数 subsets 的每次递归调用中，集合 N 的一个元素被删除，直到我们剩下长度为 k 的子集。换句话说，N的每个子集都是通过从N中选择一个有序的n-k元组获得的。这样做的方法数是：

这也可以通过绘制函数 subsets 的调用树来验证：第一级由单个调用组成，下一级由 n 次调用组成，然后是 n-1 次调用依此类推，直到有 n-k+1 个调用的最后一个级别。由于函数 subset 中的操作次数（递归调用除外）是常数，我们可以简单地乘以每个级别的调用次数并得到上述表达式。

注意两点：

这不是最有效的算法，因为每个子集都会生成多次。例如，(1, 2, 3) 的子集 (1) 可以通过先消去 2 再消去 3 或相反的方式产生。
代码包含以下条件：
```
if not result in finalarr and result:

    finalarr.append( result)
```
这个条件永远不会满足，因为函数 subset 总是 returns None。因此，这些代码行是多余的。

递归程序的时间复杂度以查找给定长度 (k) 的数组的所有子集

Time Complexity of Recursive Program to find all subsets of an array - of a given length (k)

python

recursion

big-o

time-complexity