这个递归Python k组合生成函数的时间复杂度

Question

我在找一个Python的k组合算法，结果在这里发现了一个很不错的例子：https://stackoverflow.com/a/2837693/553383

有人知道它的T(n)和/或时间复杂度吗？

下面是你在上面链接中找到的代码：

def choose_iter(elements, length):
    for i in xrange(len(elements)):
        if length == 1:
            yield (elements[i],)
        else:
            for next in choose_iter(elements[i+1:len(elements)], length-1):
                yield (elements[i],) + next
def choose(l, k):
    return list(choose_iter(l, k))

Answer 1

假设这个函数确实能生成所有长度为 k 的组合，那么它的时间复杂度是 O(n!/[(n-k)!k!] * k^2)。

总共有 O(n!/[(n-k)!k!]) 种 k 组合，而我们会生成每一种组合。

现在我们来看看每种组合是怎么生成的。这个过程是通过逐步创建一个元组来完成的。首先添加第一个元素，然后是第二个，接着是第三个，依此类推。

不过，创建一个长度为 k 的元组需要 O(k) 的时间，而实际上我们每次创建元组时的时间是 O(1+2+...+k)。因为 O(1+2+...+k)=O(k^2)，而我们对每个元组都这样做，所以我们可以得出这个函数的总复杂度是 O(n!/[(n-k)!k!] * k^2)。