这个递归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)。