algorithm - 这个组合生成器的时间复杂度是多少

Question

我想从一组 n 数字中生成 k 数字的所有组合，只要 k 小于或等于 Ceiling(n / c) 其中 c 是常数。这种算法在大 O 表示法中的时间复杂度是多少？复杂性是指数的、多项式的、伪多项式的还是其他的？

例如：n = 10, c = 3 10 中的 1 加上 10 中的 2 加上 10 中的 3 和 10 中的 4 的所有组合，因为 Ceiling(10/3) = 4。

标签： algorithmtime-complexitybig-ocomplexity-theory

Answer 1

有指数数量的东西要返回，因此它必须是指数的。

为了证明这一点，只要证明n choose floor(n/c)对于任何给定的 都呈指数级增长就足够了c。要证明你只需要证明log(n choose floor(n/c))是O(n)。并证明您可以使用著名的选择公式和斯特林近似。