从n个元素生成r长度无重复无排列组合的函数时间复杂度是多少

时间复杂度结论 #

该无重复、不考虑排列顺序的组合生成函数的时间复杂度为 O(C(n, r) * r)，其中C(n, r)为组合数，计算公式为 C(n, r) = n!/(r! · (n-r)!)。

推导说明 #

• 这个函数是基于回溯法实现的组合枚举逻辑：每次选中一个元素后，下一层递归仅从该元素之后的列表中选取元素，从根源上避免了生成排列不同的重复组合，最终生成的有效组合总数就是组合数C(n, r)。
• 每个有效组合从生成到打印需要累计执行r次元素增删操作、以及一次长度为r的列表遍历打印操作，单组合的处理成本为O(r)。
• 和题目中提到的允许重复、计入排列顺序的组合生成函数O(n^r)相比，本实现的复杂度低了r!倍的系数：因为r个元素的r!种不同排列，在本实现中只会对应1个唯一组合，当r为固定值时，复杂度也可以等价写为O(n^r / r!)。

内容的提问来源于stack exchange，提问作者Max Luchterhand