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

Question

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

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

Answer 1

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

要证明这一点，只需证明对于任何给定的c，n choose floor(n/c)都会以指数级的速度增长。为了证明你只需要证明log(n choose floor(n/c))就是O(n)。并证明您可以对choose和Stirling's approximation使用众所周知的公式。