该组合算法的时间复杂度 [英] Time complexity of this combination algorithms
本文介绍了该组合算法的时间复杂度的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我正在实现一种组合算法.这将从给定列表中生成长度的唯一组合.
I was implementing a combinations algorithm. This should generate unique combinations of length from the given list .
例如:
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代码以供参考.
The working python code is given below for reference.
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)
问题:
此算法的时间复杂度是多少?
What is the time complexity of this algorithm?
我从递归方程开始.
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)= ???
T(n) = ???
扩展解决方案.
此问题与生成所有组合时的复杂性不同.
我的问题是关于给定实现的时间复杂性,链接问题是关于生成所有组合的运行时间的一般问题.
My question is about the time complexity of the given implementation and the link question talks about runtime of generating all combinations in general.
推荐答案
感谢@Michael Foukarakis指出了丢失的K.
Thanks @Michael Foukarakis for pointing the missing 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(n k )运行时.
Overall we can say O(nk) runtime.
这篇关于该组合算法的时间复杂度的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文