我在实现一个组合算法。这将从给定列表中生成长度的唯一组合。
例如：
Input list [1, 2, 3, 4, 5] with k = 3
should generate output
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]
下面给出了可工作的python代码以供参考。
def my_combinations(items, k, out):
if k==0:
print out
return
for i in range(len(items)):
new_out = out[:]
new_out.append(items[i])
my_combinations(items[i+1:], k-1, new_out)
问题：
这个算法的时间复杂度是多少？
我从递推方程开始。
Base case: T(n, 0) = 1
Recurion : T(n, k) = T(n-1, k-1) + T(n-2, k-1) + T(n-3, k-1) + .. + T(0, k-1) + 1
= n * T(n-1, k-1) + 1
t（n）=？??
通过膨胀来解决。
这个问题不同于Complexity when generating all combinations。
我的问题是关于给定的实现的时间复杂度，并且链接问题谈论一般生成所有组合的运行时。
最佳答案
谢谢@michael foukarakis指点失踪的k。
Base case: T(n, 0) = 1
Recurion : T(n, k) = T(n-1, k-1) + T(n-2, k-1) + T(n-3, k-1) + .. + T(0, k-1) + 1
= n * T(n-1, k-1) + 1
扩展如下
T(n, k) = n * T(n-1, k-1) + 1
= n * (n-1) * T(n-2, k-2) + 1 + 1
= n * (n-1) * T(n-2, k-2) + 2
= n * (n-1) * (n-2) * T(n-3, k-3) + 3
...
= n * (n-1) * (n-2) * ..(n-k) T(n-k, k-k) + k
= n * (n-1) * (n-2) * ..(n-k) (1) + k
= O(n^k) (As it is a k th order polynomial)
总的来说，我们可以说O（NK）运行时。