此迭代组合算法的运行时

Question

我发现了以下算法 online，给定数组的长度 n 和 select 的索引数 k，生成所有可能的k 指数的组合。我在这里实现了它：

def combinations(n, k):
    combinations = []
    combination = [None]*k

    for i in range(k):
        combination[i] = i

    while combination[k - 1] < n:
        combinations.append(combination.copy())

        t = k - 1
        while t != 0 and combination[t] == n - k + t:
            t -= 1
        combination[t] += 1

        for i in range(t + 1, k):
            combination[i] = combination[i - 1] + 1

    return combinations


n, k = 4, 2
print(combinations(n, k))

（我知道 Python 的 itertools 可以用来生成这个，但是我的目标是在 Java 中使用它，并且只在 Python 此处是为了可读性和易于测试。）

例如，如果我们有一个数组 [0,1,2,3]（长度为 n=4）并且想要 select k=2 索引，这将产生：

[[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]

我的时间分析技能有点生疏：我将如何确定该算法的大 O 运行时间？或者，这是一个谁都认识的知名算法？

Answer 1

简单的估计是 O(choose(n,k)*k)，其中 choose(n,k)组合的数量。实际上，主 while 循环体的输入次数与答案中的项目数一样多。并且每次，两个内部循环中的每一个都在 O(k).

中完成

如果 n 和 k 存在某种特殊关系，则上限可能更严格。例如，如果 k~n/2，我相信 k 乘数消失，只留下 O(选择( n,k))。但至少对于 k=n-1 情况来说，界限很紧。

此迭代组合算法的运行时

Runtime of this iterative combinations algorithm

performance

big-o

combinatorics